18
Assumptions:
1>n nodes and m edges are there in the Graph V. V may directed or undirected both.
2>Weights of all the edges are non-negative finite numbers.
What the Dijkstra algorithm does:
------------------------
It finds all the shortest paths from a particular node s to all other vertexes.
How the Dijkstra algorithm does this:
----------------------------
At any point of time as the Algorithm runs we have 2 sets of nodes.
Set 1 has the nodes whose shortest paths from S has been discovered.
Set 2 has the nodes whose shortest paths are yet to be discovered.
Also node S has shortest path as 0.
So initially Set 1 only has a single node which is S. S has shortest path from S , which has distance 0.
We call 0 as Dijkstra score of S and denote it as D(S). We store this somewhere.
Now we inspect all the edges which cross from Set 1 to Set 2. We add D(S) to all these edges separately
and compare the results. The node V, which gives the smallest result as D(V), is included into Set 1 and excluded
from Set 2. D(V) is stored.
Similarly in the next step, all the edges from S or V which connect nodes of Set 2 are inspected separately.
Now we have 2 Dijkstra scores D(S) and D(V). So for the edges which have one end point with S
will be added to D(S) and the others will be added to D(V). The smallest result D(U) found where node is say U.
U is included in Set 1. U is excluded from Set 2. D(U) is stored.
This way the algorithm works. It stops as Set 2 is empty.
All the Dijkstra scores of the nodes are the shortest paths.
Correctness:
------------
We assume that when the (K+1)-th node is added to Set 1,
the Dijstra algorithm fails for the first time. That means that
(K+1)-th node is the first node which has the wrong shortest path from S.
We call the Dijkstra score of node K+1 as D(K+1).
So till Kth nodes all the dijkstra scores are really the shortest path.
We assume that the actual shortest path from S is not D(K+1). ---- Assumption 1
So there was an alternative path which was shorter. That means any node in this alternative
path has lesser distance from S, than value D(K+1). ---- Assumption 2
Again this alternative shortest path has somewhere crossed from Set 1 to Set 2.
Say this crossing edge connects node J. Evidently at least till J in this alternative path from S, all the nodes have their Dijkstra score as their shortest distance from S.
Here is the contradiction. From assumption 2, D(J) is always less than D(K+1).
So after K-th node was included in Set 1, K+1-th node can never be included
into Set 1 before node J. Because D(J) is less than D(K+1).
So Assumption 1 is wrong.
