迪杰斯特拉算法怎么写,我这里出了错误

using Graph: findEdges, AdjList
@enum Color begin
  White
  Grey
  Black
end

function dijkstra(graph::UnDirectedGraph{T}, startvertex::T, endvertex::T) where T
  distancemap = Dict{T, Number}()
  visitedmap = Dict{T, Color}()

  for adjlist in graph.adjlists
    visitedmap[adjlist.vertex] = White
    distancemap[adjlist.vertex] = Inf
  end

  visitedmap[startvertex] = Black
  distancemap[startvertex] = 0

  for edge in findEdges(graph, startvertex)
    visitedmap[edge.vertex] = Grey
    distancemap[edge.vertex] = edge.weight
  end

  flag = all(x -> x[2] == Black, collect(visitedmap))
  while !flag

    adjlists = filter(adjlist -> visitedmap[adjlist.vertex] == Grey, graph.adjlists)

    # here I can use heap
    heap = BinaryHeap(AdjList{T}, (adjlist, other) -> adjlist.vertex - other.vertex)
    for adjlist in adjlists
      push!(heap, adjlist)
    end

    minvertex = extract!(heap).vertex
    # minvertex = sort(adjlists, by = adjlist -> adjlist.vertex) |> first |> x -> x.vertex
    visitedmap[minvertex] = Black

    edges = filter(edge -> visitedmap[edge.vertex] != Black, findEdges(graph, minvertex))

    for edge in edges
      visitedmap[edge.vertex] = Grey
      distancemap[edge.vertex] = min(distancemap[edge.vertex],
                                     distancemap[minvertex] + edge.weight)
    end

    flag = all(x -> x[2] == Black, collect(visitedmap))
    @info "the visited map is" visitedmap
  end
  
  return distancemap[endvertex]
end

我这里早就忘了这个算法怎么写,这次重写发现结果错了

  graph = UnDirectedGraph(Char)
  for vertex in 'A':'G'
    insertVertex!(graph, vertex)
  end

  insertEdge!(graph, 'A', 'B', 5)
  insertEdge!(graph, 'A', 'C', 2)
  insertEdge!(graph, 'B', 'D', 1)
  insertEdge!(graph, 'B', 'E', 6)
  insertEdge!(graph, 'C', 'D', 6)
  insertEdge!(graph, 'C', 'F', 8)
  insertEdge!(graph, 'D', 'E', 1)
  insertEdge!(graph, 'D', 'F', 2)
  insertEdge!(graph, 'E', 'G', 7)
  insertEdge!(graph, 'F', 'G', 3)

  @show dijkstra(graph, 'A', 'G')

结果应该是 11 ,可是显示的是13

不知道哪里出错

使用DataStructures包中的优先级队列,这里有针对两个不同问题的实现:

https://cn.julialang.org/LeetCode.jl/dev/democards/problems/problems/743.network-delay-time/

https://cn.julialang.org/LeetCode.jl/dev/democards/problems/problems/778.swim-in-rising-water/

根据你的输入的形式稍作修改就可以了

备案号:京ICP备17009874号-2