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
不知道哪里出错