Show that the Dijkstra's algorithm computes correctly the shortest paths

[evinda]

Hello! (Smile)

Suppose that we are given a weighted, directed graph $G=(V,E)$ at which the edges that begin from the initial node s could also have negative weights, but the weights of all the ther edges are non-negative and there are no cycles of negative weight.

Show that the Dijkstra's algorithm computes correctly the shortest paths from the vertex s at this graph.

Could you give me a hint how we could do this? (Thinking)

 

[Future Bruno]

We can prove the correctness of Dijkstra's algorithm by showing that it satisfies the following two properties: 1) The shortest path from s to any other vertex is correctly determined.2) The distance labels at each node are monotonically non-decreasing. To show the correctness of Dijkstra's algorithm, we can use induction. We can start by proving that for a graph with just one node, the algorithm correctly computes the shortest path. Then, we can assume that the algorithm correctly computes the shortest paths from the initial node s on a graph with $n$ nodes and then prove that it correctly computes the shortest paths from the initial node s on a graph with $n+1$ nodes. This proof relies on the fact that Dijkstra's algorithm makes use of the relaxation operation which essentially "relaxes" the shortest path from s to a given vertex. Using this operation, the algorithm updates the shortest path from s to the given vertex if it finds a new path with lower cost. Thus, we can guarantee that the algorithm will always find the correct shortest path from s to a given vertex.By showing that Dijkstra's algorithm correctly computes the shortest paths from the initial node s on all graphs, we can conclude that it also works correctly on a weighted, directed graph with negative edge weights and no cycles of negative weight.