CODEWITHSUNDEEP
algorithmgraph
Suresh Krishna
Suresh Krishna

Reputation: 15

dijikstras algorithm for a node with no path

How will the Dijkstra's algorithm work when the shortest path weight are infinity or - infinity( ie if there is no path or no shortest path)?

How will triangular inequality ( d[v] = d[u] + w[u,v]) ) be true? I assume v is the target node, u is the parent (here there is no parent) and w is the weight of the edge(uv) which i think is zero.

Upvotes: 0

Views: 1282

Answers (1)

amit
amit

Reputation: 178491

If there is no parent to some node v, there is no u such that the edge (u,v) exists.

Therefore, the step d[v] = d[u] + w[u,v] will never take place, and the initial value of d[v] (which is set to infinity) will be unchanged until the algorithm halts.

In other words, the triangle inequality d[v] <= d[u] + w[u,v] is vacuous true for all the edges (u,v) in the graph.

Upvotes: 1

Related Questions