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();