#!/usr/local/bin/perl

#
# implementation of Dijkstra's algorithm to find the shortest path of
# weighted graphs, as demonstrated in Chapter 7 of "Grokking Algorithms"
# https://www.manning.com/books/grokking-algorithms
#
# In this example, variables holding the hashes for the graph, costs and
# which nodes have been processed (%graph, %costs, and %processed) are all
# global in scope.
#

use warnings;
use strict;
use v5.22;
use Data::Dumper;

# define the graph to store the neighbors and the cost to get to those
# neighbors.  We will use a hash of a hash
my %graph;
$graph{'start'}{'a'} = 6;
$graph{'start'}{'b'} = 2;

# get all the neighbors (keys) of Start:
# say join ", " => keys %{$graph{'start'}};
# get weights (values) of those edges:
# say join ", " => values %{$graph{'start'}};
# get key-value pairs for neighbors of Start
# foreach my $key (sort keys %{$graph{'start'}}) {
#     say "$key => $graph{'start'}{$key}";
# }

# add the rest of the nodes and their neighbors to the graph
$graph{'a'}{'fin'} = 1;
$graph{'b'}{'a'}   = 3;
$graph{'b'}{'fin'} = 5;

# define costs table
my %costs = (
        a   => 6,
        b   => 2,
        fin => 'inf',
);

# define hash table for the parents
my %parents = (
        a   => 'start',
        b   => 'start',
        fin => 'none',
);

# hash to track all of the nodes we have already processed
my %processed;

sub find_lowest_cost_node {
    # set lowest cost to infinity for initial comparison
    my $lowest_cost = 'inf';
    # set default lowest cost node to None in case none if sound
    my $lowest_cost_node = 'None';
    # for each node in our costs table
    foreach my $node (keys %costs) {
        my $cost = $costs{$node};
        # check if node is lowest cost so far AND
        # it has not yet been processed by our main while loop
        if ($cost < $lowest_cost && !exists $processed{$node}) {
            # if it is, update our $lowest_cost and $lowest_cost_node
            $lowest_cost      = $cost;
            $lowest_cost_node = $node;
        }
    }
    # will return None if all nodes have been processed
    return $lowest_cost_node;
}

my $node = find_lowest_cost_node;

while ($node ne 'None') {
    my $cost = $costs{$node}; # cost to get to current node
    my @neighbors = keys %{$graph{$node}}; # neighbors of node
    # go through all neighbors of this node
    foreach my $neighbor (@neighbors) {
        # calculate new cost of getting to neighbor via this node
        my $new_cost = $cost + $graph{$node}{$neighbor};
        # if it's cheaper to get to this neighbor through this node
        if ($costs{$neighbor} > $new_cost) {
            # update new cost for the neighbor
            $costs{$neighbor} = $new_cost;
            # the current node becomes the parent of the neighbor
            $parents{$neighbor} = $node;
        }
    }
    # mark the node as processed
    $processed{$node} = 1;
    # find the next node to process
    $node = find_lowest_cost_node;
}

# @path if our array holding the shortest path
# we build it up starting from the end ('fin') and append the coresponding
# parent ($parents{$path[0]}) to the FRONT of the array until we reach the
# beginning ('start')
my @path = ('fin');
unshift @path => $parents{$path[0]} while ($path[0] ne 'start');
say "weight of shortest path is $costs{'fin'}";
say "which is achieved by the following path:";
say join " -> " => @path;