Question

Consider a directed graph in which the only negative edges are those that leaves; all other edges are positive. Can Dijkstra's algorithm, started at s, fail on such a graph? Prove your answer.

Short answer

No, Dijkstra’s algorithm works for a directed graph that have negative edges leaving the source vertex only.

Step-by-step solution

Step-1: Define Dijkstra’s Algorithm

Dijkstra’s algorithm is a single-source shortest path problem. It is used in both directed and undirected graph with non negative weight.

Dijkstra's method to find shortest path:

1. Begin the initialization process at the root node.
2. Update the cost of the adjacent nodes in the table by identifying the adjacent nodes.
3. From the table, find the node with the lowest cost and repeat step 2 until all nodes have been traversed.

Step-2: Prove that Dijkstra’s algorithm does not fails for a graph containing negative edges at source only

Dijkstra algorithm does not take the negative edges leaving the source node into account while finding the shortest path to another vertices or nodes of the graph. For two nodes, a and b, in the graph, all the edges in the graph are assumed positive when $dist\left[a\right]>dist\left[b\right]$ is a contradictions. There cannot be a edge with negative weight from ato b.

In directed graphs with source having negative edges, it continues to be a contradiction. Otherwise, there is a negative weight path using negative edge from a to b. And this edge is from source. It means $dist\left[a\right]>dist[a,s]$, which is not possible.

Thus, Dijkstra algorithm does not fail, started at s, on a directed graph with negative edges leaving s.