By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
428,839 Members | 2,270 Online
Bytes IT Community
Submit an Article
Got Smarts?
Share your bits of IT knowledge by writing an article on Bytes.

The correctness of Dijkstra's Algorithm

P: 18
Please see the attachment also!

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.

Attached Images
File Type: jpg Dijkstra_correctness.jpg (14.5 KB, 829 views)
Aug 31 '13 #1
Share this Article
Share on Google+
2 Comments


kudos
Expert 100+
P: 126
Ok, let me get this right?

This is your claim. You have a graph. You have two point, a start point and an end end point. You run Djikstras shortest path algorithm, so you find one the shortest path between the start and end point. Let's call this path A.

Then, you insert another node into the graph, and tell us that A is no longer the shortest path?

Have I understood the claim right? Then it is a bit unfair to the algorithm, don't you think?

Also

"It finds all the shortest paths from a particular node s to all other vertexes."

This is wrong, it find the shortest path between two points, not all of them. Finding for instance the shortest path between a start point and the rest of the vertices (shortest route) sounds like a different (and much harder) problem.
Sep 3 '13 #2

P: 18
Hi Kudos,

Thanks for your comment.
Let me tell you that there was slight mistake in your understanding.

First thing is that I am not inserting any other node in the graph. It has n number of nodes from the biginning. This n is constant.

What the Algorithm is doing is that it is maintaining two disjoint subsets of nodes which we call Set 1 and Set 2.
Set 1 only maintains the nodes which have their shortest paths already calculated.
Initially Set 1 has 0 elements (nodes). Set 2 has n elements.
As the algorithm completes Set 1 has n elements and Set 2 has 0 elements.

secondly: I guess it computes all the shortest paths to other nodes from S. If there is a duplicate shortest path that won't be discovered.

Hope I am able to make it clear. Please let me know if there is any more confusion.

Regards
Sep 3 '13 #3