commit d5b2531aa34829a42d71ddfa5e67ef4a9d5439ec
parent 888c793c53ef3aada8482d3a6028030963c99487
Author: Samir Parikh <noreply@samirparikh.com>
Date: Mon, 3 Jan 2022 02:25:23 +0000
update to allow neighbors to both top and left (in addition to right and down as previously implemented)
Diffstat:
1 file changed, 26 insertions(+), 65 deletions(-)
diff --git a/dijkstra_shortest_path.pl b/dijkstra_shortest_path.pl
@@ -11,7 +11,6 @@ use v5.22;
# ignore when we are processing the neighbors of a node during our graph
# traversal
use constant LIMIT => 10;
-use Data::Dumper;
sub get_filehandle {
if (@ARGV !=1) {
@@ -32,18 +31,17 @@ sub define_matrix {
}
sub init_graph_costs {
- #my ($matrix_ref, $graph_ref, $costs_ref) = @_;
my $matrix_ref = shift;
my @mat = @{ $matrix_ref };
my %grph;
my %csts;
- my $r = scalar @mat;
+ my $r = scalar @mat;
my $c = scalar @{ $mat[0] };
- print Dumper (\@mat);
foreach my $row (0 .. $r - 2) {
foreach my $col (0 .. $c - 2) {
$csts{$row, '-', $col} = 'inf';
- foreach my $neighbor ([0, 1], [1, 0]) {
+ foreach my $neighbor ([0, 1], [1, 0], [0, -1], [-1, 0]) {
+ print "i";
my $n_row = $row + $neighbor->[0];
my $n_col = $col + $neighbor->[1];
$grph{$row, '-', $col}{$n_row, '-', $n_col} = $mat[$n_row][$n_col]
@@ -52,70 +50,27 @@ sub init_graph_costs {
}
}
$grph{'start'}{0, '-', 0} = $mat[0][0]; # start node to 0, 0
- $grph{2, '-', 2}{'end'} = 0; # n, n node to end
+ $grph{$r - 2, '-', $c - 2}{'end'} = 0; # n, n node to end
$csts{0, '-', 0} = $mat[0][0];
$csts{'end'} = 'inf';
- say "within the subroutine...";
- print Dumper (\%grph);
- print Dumper (\%csts);
- #$parents{0, '-', 0} = 'start';
return (\%grph, \%csts);
}
-my $filehandle = get_filehandle();
-my @matrix = define_matrix($filehandle);
-#print Dumper (\@matrix);
-#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 $columns = $rows;
-#my %graph;
-#my %costs;
-my %parents;
-$parents{0, '-', 0} = 'start';
-# hash to track all of the nodes we have already processed
-my %processed;
-#init_graph_costs(\@matrix, \%graph, \%costs);
-my ($graph_ref, $costs_ref) = init_graph_costs(\@matrix);
-my %graph = %{ $graph_ref };
-my %costs = %{ $costs_ref };
-#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; # n, n node to end
-#$costs{0, '-', 0} = $matrix[0][0];
-#$costs{'end'} = 'inf';
-#$parents{0, '-', 0} = 'start';
-say "after the subroutine...";
-print Dumper (\%graph);
-print Dumper (\%costs);
-
sub find_lowest_cost_node {
+ my ($costs_ref, $processed_ref) = @_;
+ my %csts = %{ $costs_ref };
+ my %proc = %{ $processed_ref };
# 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};
+ foreach my $node (keys %csts) {
+ #print "f";
+ my $cost = $csts{$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 ($cost < $lowest_cost && !exists $proc{$node}) {
# if it is, update our $lowest_cost and $lowest_cost_node
$lowest_cost = $cost;
$lowest_cost_node = $node;
@@ -125,36 +80,42 @@ sub find_lowest_cost_node {
return $lowest_cost_node;
}
-my $node = find_lowest_cost_node;
+# initialize variables
+my $filehandle = get_filehandle();
+my @matrix = define_matrix($filehandle);
+my ($graph_ref, $costs_ref) = init_graph_costs(\@matrix);
+my %graph = %{ $graph_ref };
+my %costs = %{ $costs_ref };
+my %parents;
+$parents{0, '-', 0} = 'start';
+# hash to track all of the nodes we have already processed
+my %processed;
+my $node = find_lowest_cost_node(\%costs, \%processed);
while ($node ne 'None') {
+ say "processing node $node";
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;
+ $node = find_lowest_cost_node(\%costs, \%processed);
}
+print "\n";
+
# @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
