algorithms

commit 90f51b997be6f411db84363e505cbbbcd3547bb4
parent 5047a8102f37325e136fbbb40533c223e3e1cb33
Author: Samir Parikh <noreply@samirparikh.com>
Date:   Mon,  3 Jan 2022 13:43:27 +0000

final cleanup and add comments

Diffstat:
M
dijkstra_shortest_path.pl
 | 
23
+++++++++++++----------

1 file changed, 13 insertions(+), 10 deletions(-)
diff --git a/dijkstra_shortest_path.pl b/dijkstra_shortest_path.pl
@@ -35,23 +35,29 @@ sub init_graph_costs {
     my @mat = @{ $matrix_ref };
     my %grph;
     my %csts;
-    my $r = scalar @mat;
-    my $c = scalar @{ $mat[0] };
+    my $r = scalar @mat;                # number of rows
+    my $c = scalar @{ $mat[0] };        # number of columns
     foreach my $row (0 .. $r - 2) {
         foreach my $col (0 .. $c - 2) {
-            $csts{$row, '-', $col} = 'inf';
+            $csts{$row, '-', $col} = 'inf'; # set initial costs to infinity
             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];
+                # here we set the weights of each edge between the nodes
+                # the weight is equal to the "to" node unless we've hit a
+                # boundary row or column
                 $grph{$row, '-', $col}{$n_row, '-', $n_col} = $mat[$n_row][$n_col]
                     unless ($mat[$n_row][$n_col] == LIMIT);
             }
         }
     }
-    $grph{'start'}{0, '-', 0} = $mat[0][0]; # start node to 0, 0
-    $grph{$r - 2, '-', $c - 2}{'end'}   = 0; # n, n node to end
+    # initialize the starting edge, from "start" to the first node (0, 0)
+    $grph{'start'}{0, '-', 0} = $mat[0][0];
+    # initialize the last edge, from the last node to "end"
+    $grph{$r - 2, '-', $c - 2}{'end'}   = 0;
+    # the "cost" to get to the first node is the value of the first node
     $csts{0, '-', 0}          = $mat[0][0];
+    # set initial cost to get to the "end" node to infinity
     $csts{'end'}              = 'inf';
     return (\%grph, \%csts);
 }
@@ -66,7 +72,6 @@ sub find_lowest_cost_node {
     my $lowest_cost_node = 'None';
     # for each node in our costs table
     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
@@ -87,13 +92,13 @@ my ($graph_ref, $costs_ref) = init_graph_costs(\@matrix);
 my %graph                   = %{ $graph_ref };
 my %costs                   = %{ $costs_ref };
 my %parents;
+# the parent of the first node will always be "start"
 $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
     # go through all neighbors of this node
@@ -114,8 +119,6 @@ while ($node ne 'None') {
     $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