Dijkstra\'s algorithm below finds the length of a shortest path from vertex a to

Question

Dijkstra's algorithm below finds the length of a shortest path from vertex a to vertex z. Using the supplied pseudocode, modify the algorithm to find the lengths of the shortest paths from any given vertex to every other vertex in a connected weighted graph:

This algorithm finds the length of a shortest path from vertex a to vertex z in a connected, weighted graph. The weight of edge (i, j) is w(i, j ) > 0 and the label of vertex x is L(x). At termination, L(z) is the length of a shortest path from a to z.

Input: A connected, weighted graph in which all weights are positive;

vertices a and z

Output: L(z), the length of a shortest path from a to z

dijkstra(w, a, z, L)

{

L(a) = 0

for all vertices x = a

L(x) =?

T = set of all vertices

T is the set of vertices whose shortest distance from a has

// not been found

while (z ? T )

{

choose v ? T with minimum L(v)

T = T ? {v}

for each x ? T adjacent to v

L(x) = min{L(x), L(v) + w(v, x)}

}

}

Explanation / Answer

Dear Student,

Please find the modified algorithm :

Algorithm Dijkstra(Graph, source):

create vertex set Q

for each vertex v in Graph: // Initialization
dist[v] ? INFINITY // Unknown distance from source to v
prev[v] ? UNDEFINED // Previous node in optimal path from source
add v to Q // All nodes initially in Q (unvisited nodes)

dist[source] ? 0 // Distance from source to source
  
while Q is not empty:
u ? vertex in Q with min dist[u] // Node with the least distance
// will be selected first
remove u from Q
  
for each neighbor v of u: // where v is still in Q.
alt ? dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] ? alt
prev[v] ? u

return dist[], prev[]

Happy Learning !

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.