I havethis Perl module project.

My implementation of the Dijkstra's algorithm follows:

package BidirectionalDijkstra::AlgorithmSelector;use BidirectionalDijkstra::SourceVertexSelector;use BidirectionalDijkstra::TargetVertexSelector;use BidirectionalDijkstra::Graph;sub new {    my $class = shift;    my $data = shift;    bless($data, $class);    return $data;}sub tracebackPathUnidirectional {    my $parent_map = shift;    my $target_vertex = shift;    my $path = [];    my $current_vertex = $target_vertex;        while (defined($current_vertex)) {        push(@{$path}, $current_vertex);        $current_vertex = $parent_map->{$current_vertex};    }    return [ reverse @{$path} ];}sub slow {    my $data = shift;    my $graph = $data->{graph};    my $source = $data->{source_vertex_id};    my $target = $data->{target_vertex_id};    my $search_frontier = BidirectionalDijkstra::DaryHeap->new(4);    my $settled_vertices = {};    my $distance_map = {};    my $parent_map = {};    $search_frontier->add($source, 0.0);    $distance_map->{$source} = 0.0;    $parent_map->{$source} = undef;    while ($search_frontier->size() > 0) {        my $current_vertex = $search_frontier->extractMinimum();        if ($current_vertex eq $target) {            return tracebackPathUnidirectional($parent_map, $current_vertex);        }        if (exists $settled_vertices->{$current_vertex}) {            next;        }        $settled_vertices->{$current_vertex} = undef;            foreach my $child_vertex_id (keys %{$graph->getChildren($current_vertex)}) {            if (exists $settled_vertices->{$child_vertex_id}) {                next;            }            my $tentative_distance = $distance_map->{$current_vertex} +                          $graph->getEdgeWeight($current_vertex,                                        $child_vertex_id);            my $do_update = 0;            if (not exists $distance_map->{$child_vertex_id}) {                $search_frontier->add($child_vertex_id, $tentative_distance);                $do_update = 1;            } elsif ($distance_map->{$child_vertex_id} > $tentative_distance) {                $search_frontier->decreasePriority($child_vertex_id,                                    $tentative_distance);                $do_update = 1;            }            if ($do_update) {                $distance_map->{$child_vertex_id} = $tentative_distance;                $parent_map->{$child_vertex_id} = $current_vertex;            }        }    }    return undef;}1;

Critique request

Please, tell me anything that comes to mind, thanks!

Running instruction

Clone the repository linked at the top of the post to, say, directoryBDG. FromBDG,cd toBidirectionalDijkstra-Graph, and there, run the following commands:

perl Makefile.PLmakemake test

You should see the line at the bottom of outputResult: PASS

Then, fromBDG, simply run./benchmark.pl to see the Dijkstra's algorithm in action. You may see something like this:

Graph built in 3246 seconds.Source vertex: 27843Target vertex: 18511Slow: 100000, 27843 -> 18511Dijkstra's algorithm in 9354 milliseconds.Shortest path:1: 278432: 644863: 107894: 173715: 744806: 294097: 24438: 973959: 4788810: 1452011: 6716912: 18511

• \$\begingroup\$(@200_success: What has induced removing tagdijkstra?)\$\endgroup\$

  greybeard

  – greybeard

  2022-04-15 15:07:50 +00:00

  CommentedApr 15, 2022 at 15:07
• \$\begingroup\$@greybeard Deprecated tag; see the edit log.\$\endgroup\$

  200_success

  – 200_success

  2022-04-15 15:13:15 +00:00

  CommentedApr 15, 2022 at 15:13

0

Start asking to get answers

Find the answer to your question by asking.

Explore related questions

See similar questions with these tags.