Question

Consider the problem of finding the shortest paths in a weighted directed graph using Dijkstra's algorithm. Denote the set of vertices as V, the number of vertices as |V|, the set of edges as E, and the number of edges as |E|. Answer the following questions.

Below is a pseudo-code of the algorithm that computes the length c[v] of the shortest path from the start node s to each node v. Answer code to fill in the blank _______ .

Answer 1

Ans=code for a

if c(v) + d(u,v) < c(u)

update c(u)= c(v) + d(u,v)

Dijkstra’s algorithm finds a shortest path tree from a single source node, by building a set of nodes that have minimum distance from the source.

In this algorithm-

c, an array of distances from the source node s to each node in the graph initially c(s) = 0; and for all other nodes v, c(v)= ∞

Q, a queue of all nodes in the graph

While Q is not empty,

1=pop the node v from Q with smallest d(v)(In the first run, source node s will be chosen because c(s) was initialized to 0. In the next run, the next node with the smallest c(v) value is chosen.)

2= If c(v) + d(u,v) < c(u) update c(u) to minimal distance value otherwise not

Now c will contain the smallest path