Finding shortest time or distance with Graph::Undirected

The [Graph](https://metacpan.org/pod/Graph) module on CPAN is mostly well documented. One place it falls short is explaining that not only can you create weighted edges, you can also use various edge attributes to calculate different minimum spanning trees (via Dijkstra's algorithm) based on any given attribute.

Here we create a small network of railway lines between cities, from the example on page 9 in John Armstrong's "Track Planning for Realistic Operation" (Kalmbach Books, 1986):

* There are two routes from A to D: A-B-D, and A-C-D.

* Here we assume that the route via B is longer but faster, and via
  C shorter but slower.

* The line continues from D through E and G to H.

* There is a branch line from E to F.

We calculate the shortest route by distance, and then by time.

Note the undocumented attribute parameter to SPT_Dijkstra().

#!/usr/bin/env perl
use strict;
use warnings;

use Graph::Undirected;

my $station_graph = Graph::Undirected->new();

# Add a few cities

$station_graph->add_path(qw(A B D E G H)); # first route via B
$station_graph->add_path(qw(A C D));       # second via C
$station_graph->add_path(qw(E F));         # branch route

# Define characteristics of the alternate routes

# Longer but faster
$station_graph->set_edge_attribute(qw(A B distance), 150);
$station_graph->set_edge_attribute(qw(A B time), 3.1);

# Shorter yet slower
$station_graph->set_edge_attribute(qw(A C distance), 120);
$station_graph->set_edge_attribute(qw(A C time), 3.3);

# Find spanning tree in distance
my $sptg1 = $station_graph->SPT_Dijkstra(attribute => 'distance');

print "Shortest Distance: ". join('|',$sptg1->SP_Dijkstra('A','H'));
print "\n";

# Clear cache (required for recalculation)
$station_graph->SPT_Dijkstra_clear_cache();

# Find spanning tree in time
my $sptg2 = $station_graph->SPT_Dijkstra(attribute => 'time');

print "Shortest Time:     ". join('|',$sptg2->SP_Dijkstra('A','H'));
print "\n";

1;

When run, this shows as follows:

$ perl Graph.pl 
Shortest Distance: A|C|D|E|G|H
Shortest Time:     A|B|D|E|G|H

If you want to use a directed graph, create the graph by replacing that line with:

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

and be sure to specify the starting node for the spanning trees:

my $sptg1 = $station_graph->SPT_Dijkstra(attribute => 'distance', first_root => 'A');
…
my $sptg2 = $station_graph->SPT_Dijkstra(attribute => 'time', first_root => 'A');