# SSSP_Dijkstra
#
#       $SSSP = $G->SSSP_Dijkstra($s)
#
#       Returns the single-source shortest paths (as a graph)
#       of the graph $G starting from the vertex $s using Dijktra's
#       SSSP algorithm.
#
sub SSSP_Dijkstra {
    my ( $G, $s ) = @_;

    use Heap::Fibonacci;
    my $heap = Heap::Fibonacci->new;
    my ( %in_heap, %weight, %parent );

    # The other weights are by default undef (infinite).
    $weight{ $s } = 0;

    $G->_heap_init($heap, $s, \%in_heap, \%weight, \%parent );

    # Walk the edges at the current BFS front
    # in the order of their increasing weight.
    while ( defined $heap->minimum ) {
        my $u = $heap->extract_minimum;
        delete $in_heap{ $u->vertex };

        # Now extend the BFS front.
        my $uw = $u->weight;

        foreach my $v ( $G->successors( $u->vertex ) ) {
            if ( defined( $v = $in_heap{ $v } ) ) {
                my $ow = $v->weight;
                my $nw =
                  $G->get_attribute( 'weight', $u->vertex, $v->vertex ) +
                    ($uw || 0); # The || 0 helps for undefined $uw.

                # Relax the edge $u - $v.
                if ( not defined $ow or $ow > $nw ) {
                    $v->weight( $nw );
                    $v->parent( $u->vertex );
                    $heap->decrease_key( $v );
                }
            }
        }
    }

    return $G->_SSSP_construct( $s, \%weight, \%parent );
}

# _SSSP_construct
#
#       $SSSP = $G->_SSSP_construct( $s, $W, $P );
#
#       (INTERNAL USE ONLY)
#       Return the SSSP($s) graph of graph $G based on the computed
#       anonymous hashes for weights and parents: $W and $P.
#       The vertices of the graph will have two attributes: "weight",
#       which tells the length of the shortest single-source path,
#       and "path", which is an anymous list containing the path.
#
sub _SSSP_construct {
    my ($G, $s, $W, $P ) = @_;
    my $SSSP = (ref $G)->new;

    foreach my $u ( $G->vertices ) {
        $SSSP->add_vertex( $u );

        $SSSP->set_attribute( "weight", $u, $W->{ $u } || 0 );

        my @path = ( $u );
        if ( defined $P->{ $u } ) {
            push @path, $P->{ $u };
            if ( $P->{ $u } ne $s ) {
                my $v = $P->{ $u };

                while ( $v ne $s ) {
                    push @path, $P->{ $v };
                    $v = $P->{ $v };
                }
            }
        }
        $SSSP->set_attribute( "path",   $u, [ reverse @path ] );
    }

    return $SSSP;
}

use Graph::Directed;

my $g = Graph::Directed->new();

$g->add_weighted_path(qw(a 1 b 4 c 1 d));
$g->add_weighted_path(qw(a 3 f 1 e 2 d));
$g->add_weighted_edges(qw(a 2 c  a 4 d  b 2 e  f 2 d));

my $SSSP = $g->SSSP_Dijkstra("a");

foreach my $u ( $SSSP->vertices ) {
    print "$u ",  $SSSP->get_attribute("weight", $u),
          " ", @{ $SSSP->get_attribute("path",   $u) }, "\n"
}