commit 68a678d5708957f8d3d949c439b0f5e4722293c0
parent 40227efe85a06ca45965a35a4343e1df0342a8df
Author: Samir Parikh <noreply@samirparikh.com>
Date: Mon, 3 Jan 2022 00:07:57 +0000
get initial version of algorithm to work on 3x3 matrix with a lot of superflous/testing comments
Diffstat:
1 file changed, 107 insertions(+), 0 deletions(-)
diff --git a/dijkstra_shortest_path.pl b/dijkstra_shortest_path.pl
@@ -0,0 +1,107 @@
+#!/usr/bin/env perl
+
+use strict;
+use warnings;
+use v5.22;
+use constant LIMIT => 10;
+use Data::Dumper;
+
+sub get_filehandle {
+ if (@ARGV !=1) {
+ die "Usage: $0 [input-filename]";
+ }
+ my $input_filename = $ARGV[0];
+ open my $filehandle, '<', $input_filename or
+ die "Could not open input file $input_filename: $!";
+ return $filehandle;
+}
+
+my $filehandle = get_filehandle();
+my @matrix = map{ [m/\d/g, LIMIT] } <$filehandle>; # add extra column of 9s
+my $columns = @{$matrix[0]};
+push @matrix => [ (LIMIT) x $columns ]; # add extra row of 9s
+my $rows = @matrix;
+my %graph;
+my %costs;
+my %parents;
+# hash to track all of the nodes we have already processed
+my %processed;
+
+print Dumper (\@matrix);
+foreach my $row (0 .. $rows - 2) {
+ foreach my $col (0 .. $columns - 2) {
+ $costs{$row, '-', $col} = 'inf';
+ foreach my $neighbor ([0, 1], [1, 0]) {
+ my $n_row = $row + $neighbor->[0];
+ my $n_col = $col + $neighbor->[1];
+ $graph{$row, '-', $col}{$n_row, '-', $n_col} = $matrix[$n_row][$n_col]
+ unless ($matrix[$n_row][$n_col] == LIMIT);
+ }
+ }
+}
+$graph{'start'}{0, '-', 0} = $matrix[0][0]; # start node to 0, 0
+$graph{2, '-', 2}{'end'} = 0; # end node to n, n
+$costs{0, '-', 0} = $matrix[0][0];
+$costs{'end'} = 'inf';
+$parents{0, '-', 0} = 'start';
+print Dumper (\%graph);
+
+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
+ say "current node is $node. current cost is $cost";
+ say "neighbors are @neighbors";
+ # go through all neighbors of this node
+ foreach my $neighbor (@neighbors) {
+ # calculate new cost of getting to neighbor via this node
+ say "evaluating neightbor $neighbor whose current cost is $costs{$neighbor}";
+ my $new_cost = $cost + $graph{$node}{$neighbor};
+ say "the new cost to get to $neighbor via $node is ($cost + $graph{$node}{$neighbor}) $new_cost";
+ # 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;
+ say "it's cheaper to get to $neighbor via $node";
+ say "new cost is $new_cost";
+ }
+ say "------------------";
+ }
+ # mark the node as processed
+ $processed{$node} = 1;
+ # find the next node to process
+ $node = find_lowest_cost_node;
+}
+
+# @path is 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 = ('end');
+unshift @path => $parents{$path[0]} while ($path[0] ne 'start');
+say "weight of shortest path is $costs{'end'}";
+say "which is achieved by the following path:";
+say join " -> " => @path;