what is wrong with my Dijkstram algorithm?

Michael Z. has asked for the wisdom of the Perl Monks concerning the following question:

Hi all. I have an weighted graph for protien nodes. and I was writing a perl program to find the shortest path for a given node using the Dijkstra Algorithm. each protein(vertex) has equal weight. but my program doesn't stop iterating and doesn't give me an out put. I don't know which code is bringing me the error.

the idea is to accept the name of the protein node from the user and start searching the shortest path by taking the given protien as a root node.

thanks for helping me.

regards,

Michael Z.

sub dijkstra {  
        print "Enter a node\n";  
        my $root= <>;  
        my $infinity = "inf";  
        my %graph= %graph;  
        my %dist;  
        my %prev;  
        ############################ the algorithm ####  
        # first, set all distances to infinity  
        foreach $n (keys %graph) { $dist{$n} = $infinity; $prev{$n}=$n
+; }  
        # .. except the source  
        $dist{$root} = 0;  
        # loop while we have unsolved nodes  
        # sort unsolved by distance from root  
        foreach my $n1 (sort keys %graph) {  
            foreach my $n2 (keys %{$graph{$n1}}) {  
            if (($dist{$n2} eq $infinity) ||  
            ($dist{$n2} > ($dist{$n1} + $graph{$n1}{$n2}) )) {  
                $dist{$n2} = $dist{$n} + $graph{$n1}{$n2};  
                $prev{$n2} = $n1;  
                }  
            }  
        }  

        ##### print the solutions ######  
        my $path;  
        foreach $n(keys %graph) {   
            my $t = $n;  
            $path = $t;  
            while ($t ne $root) { $t = $prev{$t}; $path = "$t -> " . $
+path; }  
            print "$n\t$dist{$n}\t$path\n";  
        }  
    }  
    dijkstra();
[download]

Comment on what is wrong with my Dijkstram algorithm? Download Code

Replies are listed 'Best First'.
Re: what is wrong with my Dijkstram algorithm? by zwon (Abbot) on Dec 28, 2011 at 11:47 UTC
You are not using strict and warnings for starters. Next: `my $root= <>;` [download] You should chomp it, otherwise `$root` will contain newline in the end. `my %graph= %graph;` [download] Oh, really? `$dist{$n2} = $dist{$n} + $graph{$n1}{$n2};` [download] And this is why you should use strict, note `$dist{$n}`, shouldn't it be `$dist{$n1}`?	[reply] [d/l] [select]
Re: what is wrong with my Dijkstram algorithm? by choroba (Cardinal) on Dec 28, 2011 at 13:14 UTC
Crossposted at Stackoverflow.	[reply]
Re: what is wrong with my Dijkstram algorithm? by JavaFan (Canon) on Dec 28, 2011 at 19:28 UTC
This is how I would write Dijkstra's algorithm. # # Takes a graph and a root element as arguments. # The graph is a doubled keyed hash, with # $graph{a}{b} = x; # indicating there's an edge from a to b with distance x. # # If the graph is supposed to be bidirectional, make sure that # for all a, b, $graph{a}{b} = $graph{b}{a}. # sub dijkstra { my $graph = shift; my $root = shift; my %dist; # Distance to root element. my @todo = [$root, 0]; { my ($to, $distance) = @{shift @todo}; unless (exists $dist{$to}) { # # Have not been here # $dist{$to} = $distance; @todo = sort {$$a[1] <=> $$b[1]} @todo, map {[$_, $distance + $$graph{$to}{$_}]} keys %{$$ +graph{$to}}; } } return \%dist; } [download] How does it work? `%dist` keeps track of which nodes with can reach from the root node, and the length of the shortest path. `@todo` is a list of nodes and their distance from the root that we know we can reach, ordered by distance from the root. If the first element of `@todo` is already in `%dist`, we've already found a shortest path to said node, and we continue with the next. Else, we have discovered a shortest path. In that case, put all neighbours, with their distances, in `@todo`, and record the distance of this node in `%dist`. Dijkstra's algorithm can be implemented in `O(N log N)` time (with `N` the number of edges in the graph), but the above isn't -- you'd need a binary search tree (or another datastructure) which does inserts and extract-minimum operations in (amortized) `O(log N)` time. The above implementation is lazy, and uses arrays and sort to keep an ordered list, resulting in an `O(N²)` run time. (Note that it isn't `O(N² log N)` as Perls merge sort implementation is smart enough to take the fact that `@todo` is sorted already into account). Update: fixed a bug in the algorithm.	[reply] [d/l] [select]
Re^2: what is wrong with my Dijkstram algorithm? by Michael Z. (Initiate) on Dec 29, 2011 at 03:59 UTC
thanks Java Fan, but can you show me how to work with the following example. `%graph = ( 'ARR1' => {'ARR1' => 1,'CHOP' => 1,'CIN5' => 1}, 'MET4' => {'cJun' => 1,'OASIS' => 1,'cMaf'=> 1,'cJun' => 1}, 'JunD' => {'OASIS' => 1,'MafK' => 1,'NFE2'=> 1,'p21SNFT' => 1}, 'MafB' => {'MafB' => 1,cMaf => 1}, 'MafG'=> {'MafG' => 1,'MafK' => 1,NFE2=> 1,'NFE2L1' => 1}, );` [download] I have a graph like this with 57 unique protein(node) linked to a minimum of 1 which is linked to it self. these are samples of it. and note that each node has equal weight. which is 1 thanks again Michael Z.	[reply] [d/l]
Re^3: what is wrong with my Dijkstram algorithm? by JavaFan (Canon) on Dec 29, 2011 at 09:11 UTC
What have you tried? What is unclear to my explanation of how the dijkstra routine should be called? Do you actually want Dijkstras algorithm, or do you need an "all shortest paths" algorithm?	[reply]
how can i print a graph path with so many linkages by Michael Z. (Initiate) on Dec 29, 2011 at 15:45 UTC
Re^5: what is wrong with my Dijkstram algorithm? by JavaFan (Canon) on Dec 29, 2011 at 16:09 UTC
Re: what is wrong with my Dijkstram algorithm? by RichardK (Parson) on Dec 28, 2011 at 12:02 UTC
How big is %graph? Are you sure that it's not just taking a long time to complete? You could try adding a print statement to display $n1 in the first loop, and that should show you what's happening :)	[reply]