algorithms

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

commit c0c408a450466cf4a7037048857bfab8904dfa89
parent 0f054d0ec4d84eee111878db9b43436f76c20e2d
Author: Samir Parikh <noreply@samirparikh.com>
Date:   Thu, 30 Dec 2021 21:50:26 +0000

update dijkstra with main while loop

Diffstat:
Mdijkstra.pl | 50++++++++++++++++++++++++++++++++++++++++++++++++--
1 file changed, 48 insertions(+), 2 deletions(-)

diff --git a/dijkstra.pl b/dijkstra.pl @@ -17,11 +17,57 @@ my %graph; $graph{'start'}{'a'} = 6; $graph{'start'}{'b'} = 2; -# get all the neighbors of Start: +# get all the neighbors (keys) of Start: say join ", " => keys %{$graph{'start'}}; -# get weights of those edges: +# 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 ndoes 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', +); + +# array to track all of the nodes we have already processed +my @processed; + +my $node = find_lowest_cost_node(\%costs); + +while ($node ne 'None') { + my $cost = $costs{$node}; # cost of 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 + push @processed => $node; + # find the next node to process + $node = find_lowest_cost_node(\%costs); +}