algorithms

Repository of programs that demonstrate basic algorithms I've been learning
git clone git://git.samirparikh.com/algorithms
Log | Files | Refs | README

commit e321591de625cda5199123a3293a9c7a60fd5aa9
parent c0c408a450466cf4a7037048857bfab8904dfa89
Author: Samir Parikh <noreply@samirparikh.com>
Date:   Thu, 30 Dec 2021 22:38:36 +0000

make final updates and add comments

Diffstat:
Mdijkstra.pl | 59++++++++++++++++++++++++++++++++++++++++++++++-------------
1 file changed, 46 insertions(+), 13 deletions(-)

diff --git a/dijkstra.pl b/dijkstra.pl @@ -5,6 +5,10 @@ # 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; @@ -18,17 +22,16 @@ $graph{'start'}{'a'} = 6; $graph{'start'}{'b'} = 2; # get all the neighbors (keys) of Start: -say join ", " => keys %{$graph{'start'}}; +# say join ", " => keys %{$graph{'start'}}; # get weights (values) of those edges: -say join ", " => values %{$graph{'start'}}; +# 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}"; -} +# foreach my $key (sort keys %{$graph{'start'}}) { +# say "$key => $graph{'start'}{$key}"; +# } # add the rest of the ndoes and their neighbors to the graph $graph{'a'}{'fin'} = 1; - $graph{'b'}{'a'} = 3; $graph{'b'}{'fin'} = 5; @@ -36,7 +39,7 @@ $graph{'b'}{'fin'} = 5; my %costs = ( a => 6, b => 2, - fin => "inf", + fin => 'inf', ); # define hash table for the parents @@ -46,13 +49,33 @@ my %parents = ( fin => 'none', ); -# array to track all of the nodes we have already processed -my @processed; +# 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(\%costs); +my $node = find_lowest_cost_node; while ($node ne 'None') { - my $cost = $costs{$node}; # cost of 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 foreach my $neighbor (@neighbors) { @@ -67,7 +90,17 @@ while ($node ne 'None') { } } # mark the node as processed - push @processed => $node; + $processed{$node} = 1; # find the next node to process - $node = find_lowest_cost_node(\%costs); + $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;