Dijkstra Tool with directed graphs

Submitted by fausto on Wed, 01/18/2012 - 14:01

Hello:
I'm using the dijkstra tool in order to find the shortest path in a directed graph, however this tool seem to consider every edge to be bidirectional.
For instance, lets consider this simple example:
digraph
{
    N1->N2;
    N2->N3;
    N3->N1;
}
After applying the algorithm I get that N3 is reachable with distance 1, having N1 as the previous node.
Is this supposed to happen? Any solution for this problem?
Thanks in advance. Best regards.

Add new comment

Dijkstra Tool

Submitted by Anonymous on Tue, 01/31/2012 - 16:42.

If the distance is 1 between each variable (N1N2, N2N3, N3N1) then yes, the tool is correct. If the distances between nodes varied (N1N2 = 2, N2N3 = 4, N3N1 = 7), then the shortest route from N1 to N3 would be to go through N2.

Dijkstra Tool

Submitted by erg on Thu, 02/02/2012 - 10:46.

With the given lengths, the dijkstra tool correctly finds the shortest path from N1 to N3 goes through N2 and has length 6.

In the directed case, the shortest path has to go through N2.