## DESCRIPTION
## Dijkstra's algorithm, plus keeping track of the path: full table.
## ENDDESCRIPTION

## KEYWORDS('algorithms', 'Dijkstra')

## Date('20241007')
## Author('Joseph Pedersen')
## Institution('USMA')

DOCUMENT();

loadMacros(
    "PGstandard.pl",
    "PGML.pl",
    "MathObjects.pl",
    "parserFunction.pl",
    'niceTables.pl',
    'PGtikz.pl',
    "PGcourse.pl",
);

$showPartialCorrectAnswers = 1;

Context()->strings->add(O => {}, A => {}, B => {}, C => {}, D => {}, E => {}, F => {}, G => {}, T => {}, NA => {});

@nodes = ('O', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'T');

%estimates = (
    O => 0,
    A => undef,
    B => undef,
    C => undef,
    D => undef,
    E => undef,
    F => undef,
    G => undef,
    T => undef,
);

%previous = (
    O => undef,
    A => undef,
    B => undef,
    C => undef,
    D => undef,
    E => undef,
    F => undef,
    G => undef,
    T => undef,
);

%edges = (
    OA => undef,
    OB => undef,
    OC => undef,
    OD => undef,
    AB => undef,
    BA => undef,
    BC => undef,
    CB => undef,
    CD => undef,
    DC => undef,
    AE => undef,
    BE => undef,
    BF => undef,
    CF => undef,
    CG => undef,
    DG => undef,
    EA => undef,
    EB => undef,
    FB => undef,
    FC => undef,
    GC => undef,
    GD => undef,
    EF => undef,
    FE => undef,
    FG => undef,
    GF => undef,
    ET => undef,
    FT => undef,
    GT => undef,
    TE => undef,
    TF => undef,
    TG => undef,
);
##########################################
### START of Dijkstra's algorithm ########
@solved = ();
@unsolved = ('O', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'T');
@record = ();

$maxit = 10;
while (($maxit > 0) and @unsolved) {
    $maxit -= 1;
    $closest = undef;
    $dist = 1000;
    for $u (@unsolved){
        $d = $estimates{$u};
        if (defined($d) and ($d < $dist)) {
            $closest = $u;
            $dist = $d;
        }
    }
    push (@solved, $closest);
    @unsolved = grep {$_ ne $closest;} @unsolved;

    keys %edges;
    for $k (keys %edges) {
        $v = $edges{$k};
        $from_node = substr($k, 0, 1);
        if ($closest eq $from_node) {
            $to_node = substr($k, 1, 1);
            if (exists $estimates{$to_node}) {
                $adj_est = $estimates{$to_node};
            } else {
                $adj_est = undef;
            }

            if (defined($v)) {
                if ((not defined($adj_est)) or ($adj_est > ($dist + $v))) {
                $estimates{substr($k, 1, 1)} = $dist + $v;
                $previous{substr($k, 1, 1)} = $closest;
                }
            } else {
                $shorter = (random(1,100) < 80);
    
                if (defined($adj_est)) {
                    $diff = $adj_est - $dist;
                } else {
                    $diff = 50;
                }
                @non_none = grep {defined($_) and $_ < 1000} (values %estimates);
                %cantbe = map {$_ - $dist => 1} grep {$_ > $dist} @non_none;
                %canbe = map {$_ => 1} grep {not exists $cantbe{$_}} (2..$diff);
    
                if ($diff < 2) {
                    $edges{$k} = random(2, 10);
                } elsif ($shorter and scalar keys %canbe) {
                    $edges{$k} = (random_subset(1, keys %canbe))[0];
                } else {
                    $edges{$k} = (random_subset(1, grep {not exists $cantbe{$_}} ((10)..($diff + 10))))[0];
                    $this_is = $edges{$k};
                }
    
                if ((not defined($adj_est)) or ($adj_est > ($dist + $edges{$k}))) {
                    $estimates{substr($k, 1, 1)} = $dist + $edges{$k};
                    $previous{substr($k, 1, 1)} = $closest;
                }
                $rev_e = reverse($k);
                if (exists $edges{$rev_e}) {
                    $edges{$rev_e} = $edges{$k}
                }
            }
        }
    }

    @row1 = (($closest,), map {defined($estimates{$_}) ? $estimates{$_} : "INF"} @nodes);
    @row2 = (("From",), map {defined($previous{$_}) ? $previous{$_} : "NA"} @nodes);
    push (@record, @row1);
    push (@record, @row2);
}
##########################################
### START of graph #######################
$graph_image = createTikZImage();
$graph_image->tikzLibraries("graphs, quotes");

$graph_image->BEGIN_TIKZ

  \node[shape=circle,draw] (a) at (2,3) {A};
  \node[shape=circle,draw] (b) at (2,1) {B};
  \node[shape=circle,draw] (c) at (2,-1) {C};
  \node[shape=circle,draw] (d) at (2,-3) {D};
  \node[shape=circle,draw] (e) at (4,2) {E};
  \node[shape=circle,draw] (f) at (4,0) {F};
  \node[shape=circle,draw] (g) at (4,-2) {G};
  \node[shape=circle,draw] (o) at (0,0) {O};
  \node[shape=circle,draw] (t) at (6,0) {T};

\graph [edge quotes={fill=white,inner sep=1pt}] { (o) -- [midway, "$edges{OA}"] (a);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (o) -- [midway, "$edges{OB}"] (b);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (o) -- [midway, "$edges{OC}"] (c);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (o) -- [midway, "$edges{OD}"] (d);}

\graph [edge quotes={fill=white,inner sep=1pt}] { (a) -- [midway, "$edges{AB}"] (b);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (b) -- [midway, "$edges{BC}"] (c);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (c) -- [midway, "$edges{CD}"] (d);}

\graph [edge quotes={fill=white,inner sep=1pt}] { (a) -- [midway, "$edges{AE}"] (e);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (b) -- [midway, "$edges{BE}"] (e);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (b) -- [midway, "$edges{BF}"] (f);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (c) -- [midway, "$edges{CF}"] (f);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (c) -- [midway, "$edges{CG}"] (g);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (d) -- [midway, "$edges{DG}"] (g);}

\graph [edge quotes={fill=white,inner sep=1pt}] { (e) -- [midway, "$edges{EF}"] (f);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (f) -- [midway, "$edges{FG}"] (g);}

\graph [edge quotes={fill=white,inner sep=1pt}] { (e) -- [midway, "$edges{ET}"] (t);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (f) -- [midway, "$edges{FT}"] (t);}
\graph [edge quotes={fill=white,inner sep=1pt}] { (g) -- [midway, "$edges{GT}"] (t);}

END_TIKZ
##########################################
BEGIN_PGML

>> [@ image($graph_image, width => 400, tex_size => 800) @]* <<

In Dijkstra's algorithm on a connected network of [`n`] nodes, the nodes all start as *unsolved* (aka unexplored), with an estimated distance of [`0`] on the origin and [`\infty`] (*INF*) on all other nodes. For each node, too find the path to it, instead of only the distance to it, we can also keep track of the node that the shortest path to it comes *from*, which starts as *NA* for every node.

Then, for each of [`n`] iterations, three steps are performed:

1. The unsolved node with the minimum estimated distance is marked as the newly *solved* (aka explored) node.
2. The distance estimates of the *unsolved* nodes connected to that newly solved one are updated, if necessary.  All other distance estimates stay the same.
3. If (and only if) we update a distance estimate to a node, then we change the node that the shortest path to it comes *from*.

Complete Dijkstra's algorithm and fill in the following table:

[#
 [. Solved .]
 [. [`O`] .]
 [. [`A`] .]
 [. [`B`] .]
 [. [`C`] .]
 [. [`D`] .]
 [. [`E`] .]
 [. [`F`] .]
 [. [`G`] .]
 [. [`T`] .]*
 
 [. None .]
 [. [`0`] .]
 [. INF .]
 [. INF .]
 [. INF .]
 [. INF .]
 [. INF .]
 [. INF .]
 [. INF .]
 [. INF .]*
 
 [. From: .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]{bgcolor => 'lightgray'}
 [. NA .]*{bgcolor => 'lightgray'}
 
  [. [_]{$record[0]} .]
  [. [_]{$record[1]} .]
  [. [_]{$record[2]} .]
  [. [_]{$record[3]} .]
  [. [_]{$record[4]} .]
  [. [_]{$record[5]} .]
  [. [_]{$record[6]} .]
  [. [_]{$record[7]} .]
  [. [_]{$record[8]} .]
  [. [_]{$record[9]} .]*

  [. [$record[10]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[11]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[12]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[13]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[14]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[15]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[16]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[17]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[18]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[19]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[20]} .]
  [. [_]{$record[21]} .]
  [. [_]{$record[22]} .]
  [. [_]{$record[23]} .]
  [. [_]{$record[24]} .]
  [. [_]{$record[25]} .]
  [. [_]{$record[26]} .]
  [. [_]{$record[27]} .]
  [. [_]{$record[28]} .]
  [. [_]{$record[29]} .]*

  [. [$record[30]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[31]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[32]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[33]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[34]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[35]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[36]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[37]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[38]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[39]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[40]} .]
  [. [_]{$record[41]} .]
  [. [_]{$record[42]} .]
  [. [_]{$record[43]} .]
  [. [_]{$record[44]} .]
  [. [_]{$record[45]} .]
  [. [_]{$record[46]} .]
  [. [_]{$record[47]} .]
  [. [_]{$record[48]} .]
  [. [_]{$record[49]} .]*

  [. [$record[50]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[51]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[52]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[53]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[54]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[55]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[56]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[57]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[58]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[59]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[60]} .]
  [. [_]{$record[61]} .]
  [. [_]{$record[62]} .]
  [. [_]{$record[63]} .]
  [. [_]{$record[64]} .]
  [. [_]{$record[65]} .]
  [. [_]{$record[66]} .]
  [. [_]{$record[67]} .]
  [. [_]{$record[68]} .]
  [. [_]{$record[69]} .]*

  [. [$record[70]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[71]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[72]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[73]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[74]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[75]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[76]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[77]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[78]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[79]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[80]} .]
  [. [_]{$record[81]} .]
  [. [_]{$record[82]} .]
  [. [_]{$record[83]} .]
  [. [_]{$record[84]} .]
  [. [_]{$record[85]} .]
  [. [_]{$record[86]} .]
  [. [_]{$record[87]} .]
  [. [_]{$record[88]} .]
  [. [_]{$record[89]} .]*

  [. [$record[90]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[91]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[92]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[93]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[94]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[95]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[96]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[97]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[98]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[99]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[100]} .]
  [. [_]{$record[101]} .]
  [. [_]{$record[102]} .]
  [. [_]{$record[103]} .]
  [. [_]{$record[104]} .]
  [. [_]{$record[105]} .]
  [. [_]{$record[106]} .]
  [. [_]{$record[107]} .]
  [. [_]{$record[108]} .]
  [. [_]{$record[109]} .]*

  [. [$record[110]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[111]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[112]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[113]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[114]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[115]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[116]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[117]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[118]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[119]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[120]} .]
  [. [_]{$record[121]} .]
  [. [_]{$record[122]} .]
  [. [_]{$record[123]} .]
  [. [_]{$record[124]} .]
  [. [_]{$record[125]} .]
  [. [_]{$record[126]} .]
  [. [_]{$record[127]} .]
  [. [_]{$record[128]} .]
  [. [_]{$record[129]} .]*

  [. [$record[130]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[131]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[132]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[133]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[134]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[135]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[136]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[137]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[138]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[139]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[140]} .]
  [. [_]{$record[141]} .]
  [. [_]{$record[142]} .]
  [. [_]{$record[143]} .]
  [. [_]{$record[144]} .]
  [. [_]{$record[145]} .]
  [. [_]{$record[146]} .]
  [. [_]{$record[147]} .]
  [. [_]{$record[148]} .]
  [. [_]{$record[149]} .]*

  [. [$record[150]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[151]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[152]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[153]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[154]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[155]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[156]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[157]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[158]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[159]} .]*{bgcolor => 'lightgray'}

  [. [_]{$record[160]} .]
  [. [_]{$record[161]} .]
  [. [_]{$record[162]} .]
  [. [_]{$record[163]} .]
  [. [_]{$record[164]} .]
  [. [_]{$record[165]} .]
  [. [_]{$record[166]} .]
  [. [_]{$record[167]} .]
  [. [_]{$record[168]} .]
  [. [_]{$record[169]} .]*

  [. [$record[170]] .]{bgcolor => 'lightgray'}
  [. [_]{$record[171]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[172]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[173]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[174]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[175]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[176]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[177]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[178]} .]{bgcolor => 'lightgray'}
  [. [_]{$record[179]} .]*{bgcolor => 'lightgray'}
#]{align => '|c|c|c|c|c|c|c|c|c|c|', horizontalrules => 1}


END_PGML
##########################################

ENDDOCUMENT();