in reply to Re: what is wrong with my Dijkstram algorithm?
in thread what is wrong with my Dijkstram algorithm?

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.

Replies are listed 'Best First'.
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]

      HI perl monks, I have undirected graph with 57 nodes and 204 linkages. I calculate the shortest path of all nodes with its sub nodes using Dijkstram algorithm, but I couldn't able to print the path of the nodes from a given root. here is how i tried. 

      ########## the dijkstram algorithm#################
sub dijkstra {
    my ($graph, $root) = @_;
    my (%dist, %prev);

    foreach $n (keys %{$graph}) { $dist{$n} = inf; $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 inf)) {
                $dist{$n2} = $dist{$n1} + $graph->{$n1}{$n2};
                $prev{$n2} = $n1;
            }
        }
    }
    return (\%prev, \%dist);
}
######## print the path and the distance for a given node#############
sub printPaths {
    my ($graph, $prev, $dist) = @_;
    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";
    }
}

      [download]

      the problem occurs on the while loop. when it gets a node that doesn't have the same root and when the previous node always returns the same node. please help me or give me any suggestion. thanks

[reply]
[d/l]
        Actually, I'm looking to display all possible way of a path for a given node and calculate the shortest path of all paths.
        I've no idea what you mean by that. "All possible way of a path for a given node"? What is that?
        my data seems like this.
        That doesn't seem to match the example hash you gave in your previous post.
[reply]

In Section Seekers of Perl Wisdom