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(N2) run time. (Note that it isn't O(N2 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.

In reply to Re: what is wrong with my Dijkstram algorithm? by JavaFan
in thread what is wrong with my Dijkstram algorithm? by Michael Z.

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.