Greedy algorithm to generate shortest path from vertex to all vertices in a digraph?

Answer 1

In graph theory this is called the shortest path problem. There are several algorithms to solve it. Here is the pseudo code for one of them: Yes it is a Greedy algorithm! 1 function Dijkstra(Graph, source): 2 for each vertex v in Graph: // Initializations 3 dist[v] := infinity // Unknown distance function from source to v 4 previous[v] := undefined // Previous node in optimal path from source 5 dist[source] := 0 // Distance from source to source 6 Q := the set of all nodes in Graph // All nodes in the graph are unoptimized - thus are in Q 7 while Q is not empty: // The main loop 8 u := vertex in Q with smallest dist[] 9 remove u from Q 10 for each neighbor v of u: // where v has not yet been removed from Q. 11 alt := dist[u] + dist_between(u, v) // be careful in 1st step - dist[u] is infinity yet 12 if alt < dist[v] // Relax (u,v,a) 13 dist[v] := alt 14 previous[v] := u 15 return previous[] If we are only interested in a shortest path between vertices source and target, we can terminate the search at line 10 if u = target. Now we can read the shortest path from source to target by iteration: 1 S := empty sequence 2 u := target 3 while defined previous[u] 4 insert u at the beginning of S 5 u := previous[u] here is another procedure BellmanFord(list vertices, list edges, vertex source) // This implementation takes in a graph, represented as lists of vertices // and edges, and modifies the vertices so that their distance and // predecessor attributes store the shortest paths. // Step 1: Initialize graph for each vertex v in vertices: if v is source then v.distance := 0 else v.distance := infinity v.predecessor := null // Step 2: relax edges repeatedly for i from 1 to size(vertices)-1: for each edge uv in edges: // uv is the edge from u to v u := uv.source v := uv.destination if v.distance > u.distance + uv.weight: v.distance := u.distance + uv.weight v.predecessor := u // Step 3: check for negative-weight cycles for each edge uv in edges: u := uv.source v := uv.destination if v.distance > u.distance + uv.weight: error "Graph contains a negative-weight cycle"