Shortest Path Algorithem
Dijkstra Algorithm
Introduction of Dijkstra Algorithm
Just using a priority queue, only works when all the wights of edges are positive.
Bellman Ford Algorithm
Introduction of Bellman Ford Algorithm
It works even the weight of edge is negative.
function bellmanFord(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
distance[S] <- 0
for each vertex V in G
for each edge (U,V) in G
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U
for each edge (U,V) in G
If distance[U] + edge_weight(U, V) < distance[V}
Error: Negative Cycle Exists
return distance[], previous[]