unit PathSF;
//*******************************************************
// Example program demonstrating shortest path trees
// using a label setting algorithm.
//*******************************************************
// Copyright (C) 1998 John Wiley & Sons, Inc.
// All rights reserved. See additional copyright
// information in Readme.txt.
//*******************************************************

interface

uses
  Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
  Menus;

const
    crLinkCursor = 10;
    crNodeCursor = 11;
    RADIUS = 10;
    INFINITY = 32767;
    
type
    TNodeStatus = (nsNotInList, nsWasInList, nsNowInList);
    TEditMode = (emNone, emNewNode, emDeleteNode,
        emNewLink1, emNewLink2, emDeleteLink1,
        emDeleteLink2);

    PLink = ^TLink;
    PNode = ^TNode;
    TLink = record
        Node1    : PNode;
        Node2    : PNode;
        Cost     : Integer;
        NextLink : PLink;   // Next link in the node's list of links.
        InTree   : Boolean; // Is it in the shortest path tree?
    end;
    TNode = record
        Id           : Integer;
        X            : Integer;
        Y            : Integer;
        LinkSentinel : TLink;       // Links out of this node.
        NextNode     : PNode;       // Next node in list of all nodes.
        Status       : TNodeStatus; // Has it been in the tree?
        Dist         : Integer;     // Distance from root.
        InLink       : PLink;       // The link into this node.
    end;

    // Cell for candidate linked list.
    PCandidate = ^TCandidate;
    TCandidate = record
        Node          : PNode;
        NextCandidate : PCandidate;
    end;

  TPathSForm = class(TForm)
    MainMenu1: TMainMenu;
    mnuNew: TMenuItem;
    mnuOpen: TMenuItem;
    mnuSave: TMenuItem;
    mnuSaveAs: TMenuItem;
    mnuFileSep: TMenuItem;
    mnuExit: TMenuItem;
    mnuNewNode: TMenuItem;
    mnuNewLink: TMenuItem;
    mnuDeleteNode: TMenuItem;
    mnuDeleteLink: TMenuItem;
    File1: TMenuItem;
    Edit1: TMenuItem;
    OpenNetDialog: TOpenDialog;
    SaveNetDialog: TSaveDialog;
    Help1: TMenuItem;
    mnuAbout: TMenuItem;
    procedure FormCreate(Sender: TObject);
    procedure FormDestroy(Sender: TObject);
    procedure FreeNetwork;
    procedure FormPaint(Sender: TObject);
    procedure mnuExitClick(Sender: TObject);
    procedure FormCloseQuery(Sender: TObject; var CanClose: Boolean);
    procedure mnuNewClick(Sender: TObject);
    procedure mnuOpenClick(Sender: TObject);
    procedure mnuSaveClick(Sender: TObject);
    procedure mnuSaveAsClick(Sender: TObject);
    procedure mnuNewNodeClick(Sender: TObject);
    procedure mnuNewLinkClick(Sender: TObject);
    procedure mnuDeleteNodeClick(Sender: TObject);
    procedure mnuDeleteLinkClick(Sender: TObject);
    procedure mnuAboutClick(Sender: TObject);
    function DataSafe : Boolean;
    procedure NewNetwork;
    procedure DrawNetwork;
    procedure LoadNetwork(fname : String);
    function FindNodeById(id : Integer) : PNode;
    procedure SaveNetwork(fname : String);
    procedure ResetEditMode;
    procedure FormMouseDown(Sender: TObject; Button: TMouseButton;
      Shift: TShiftState; X, Y: Integer);
    function SelectNode(X, Y : Integer) : PNode;
    procedure DeleteNode(target : PNode);
    procedure DeleteLink(n1, n2 : PNode);
    procedure RemoveLinkFromNode(n1, n2 : PNode);
    procedure CreateNode(X, Y : Integer);
    procedure CreateLink;
    procedure FindPathTree(root : PNode);
    procedure ResetPathTree;
  private
    { Private declarations }
    FileName     : String;    // Name of file loaded.
    EditMode     : TEditMode; // Click mode.
    DataModified : Boolean;   // Has the data been modified?
    NodeSentinel : TNode;     // List of all nodes.
    Node_1       : PNode;     // Nodes selected for adding a link, etc.
    Node_2       : PNode;
    MaxId        : Integer;   // Largest node Id.
    GotTree      : Boolean;   // Have we built a spanning tree?
    RootNode     : PNode;
  public
    { Public declarations }
  end;

var
  PathSForm: TPathSForm;

implementation

{$R *.DFM}

// Load some custom cursors.
procedure TPathSForm.FormCreate(Sender: TObject);
begin
    Screen.Cursors[crNodeCursor] := LoadCursor(HInstance, 'NodeCursor');
    Screen.Cursors[crLinkCursor] := LoadCursor(HInstance, 'LinkCursor');

    // Start with an empty network.
    NodeSentinel.NextNode := nil;
end;

// Free the network's dynamically allocated memory.
procedure TPathSForm.FormDestroy(Sender: TObject);
begin
    FreeNetwork;
end;

// Free the network's dynamically allocated memory.
procedure TPathSForm.FreeNetwork;
var
    node, next_node : PNode;
    link, next_link : PLink;
begin
    // Free all the nodes.
    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        // Free the node's links.
        link := node^.LinkSentinel.NextLink;
        while (link <> nil) do
        begin
            next_link := link^.NextLink;
            FreeMem(link);
            link := next_link;
        end;

        // Free the node itself.
        next_node := node^.NextNode;
        FreeMem(node);
        node := next_node;
    end;
    NodeSentinel.NextNode := nil;
end;

// Redraw the network.
procedure TPathSForm.FormPaint(Sender: TObject);
begin
    DrawNetwork;
end;

procedure TPathSForm.mnuExitClick(Sender: TObject);
begin
    Close;
end;

// Refuse to close if the data is not safe.
procedure TPathSForm.FormCloseQuery(Sender: TObject;
  var CanClose: Boolean);
begin
    CanClose := DataSafe;
end;

// Create a new network.
procedure TPathSForm.mnuNewClick(Sender: TObject);
begin
    // Make sure the current data is safe.
    if (not DataSafe) then exit;

    // Start the new network.
    NewNetwork;

    // Display the empty network.
    DrawNetwork;
end;

// Load a network file.
procedure TPathSForm.mnuOpenClick(Sender: TObject);
begin
    // Make sure the current data is safe.
    if (not DataSafe) then exit;

    // Prepare the file selection dialog
    OpenNetDialog.Options :=
        [ofHideReadOnly, ofFileMustExist];
    OpenNetDialog.FileName := '*.net';
    if (not OpenNetDialog.Execute) then exit;

    // Load the file.
    LoadNetwork(OpenNetDialog.FileName);

    // Display the network.
    DrawNetwork;
end;

// Save the file using the current FileName.
procedure TPathSForm.mnuSaveClick(Sender: TObject);
begin
    // Make sure we have a file name.
    if (FileName = '') then
    begin
        mnuSaveAsClick(Sender);
        exit;
    end;

    // Save the network.
    SaveNetwork(FileName);
end;

// Save the network in a file selected by the user.
procedure TPathSForm.mnuSaveAsClick(Sender: TObject);
begin
    // Prepare the file selection dialog
    SaveNetDialog.Options := [ofOverwritePrompt];
    SaveNetDialog.FileName := '*.net';

    // Get the user's selection.
    if (not SaveNetDialog.Execute) then exit;

    // Save the network.
    SaveNetwork(SaveNetDialog.FileName);
end;

// Prepare to get a new node.
procedure TPathSForm.mnuNewNodeClick(Sender: TObject);
begin
    EditMode := emNewNode;
    Cursor := crNodeCursor;
end;

// Prepare to get a new link.
procedure TPathSForm.mnuNewLinkClick(Sender: TObject);
begin
    EditMode := emNewLink1;
    Cursor := crLinkCursor;
end;

// Prepare to delete a node.
procedure TPathSForm.mnuDeleteNodeClick(Sender: TObject);
begin
    EditMode := emDeleteNode;
    Cursor := crNodeCursor;
end;

// Prepare to delete a link.
procedure TPathSForm.mnuDeleteLinkClick(Sender: TObject);
begin
    EditMode := emDeleteLink1;
    Cursor := crLinkCursor;
end;

procedure TPathSForm.mnuAboutClick(Sender: TObject);
const
    CRCR = #13#10#13#10;
begin
    MessageDlg(
        'This program uses a label setting shortest path algorithm to find shortest path trees.' + CRCR +
        'When you are not editing the network and you click on a node, the program finds and displays a shortest path tree rooted at that node.'
        , mtInformation, [mbOK], 0);
end;

// Return true if the data is safely saved.
function TPathSForm.DataSafe : Boolean;
const
    MB_YESNOCANCEL = $3;
    MB_ICONQUESTION = $20;
var
    status : Integer;
begin
    if (not DataModified) then
    begin
        Result := True;
        exit;
    end;

    status := Application.MessageBox(
        'Save changes to the network?',
        'Save Changes?', MB_YESNOCANCEL + MB_ICONQUESTION);
                                                                                            //Inserted by VB2D for SELECT CASE
    case status of
        IDYES:
            begin
                mnuSaveClick(nil);
                // mnuSaveClick resets DataModified appropriately.
                Result := (not DataModified);
            end;
        IDNO:
            Result := True;
    else
        // IDCANCEL:
            Result := False;
    end;
end;

// Start a new network.
procedure TPathSForm.NewNetwork;
begin
    FreeNetwork;
    MaxId := 0;

    // The new network has not yet been modified.
    ResetEditMode;
    DataModified := False;
    FileName := '';
    Caption := 'PathS []';
end;

// Display the network.
procedure TPathSForm.DrawNetwork;
var
    node                   : PNode;
    link                   : PLink;
    x1, y1, x2, y2, dx, dy : Integer;
    dist                   : Single;
    txt                    : String;
    rect                   : TRect;
    size                   : TSize;
begin
    // Erase the form.
    rect.Left := 0;
    rect.Top := 0;
    rect.Right := ClientWidth;
    rect.Bottom := ClientHeight;
    Canvas.Brush.Color := Color;
    Canvas.FillRect(rect);

    // Draw the links and nodes. Every link has a reverse
    // link so we draw those where Node2 > Node1.
    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        link := node^.LinkSentinel.NextLink;
        while (link <> nil) do
        begin
            if (Longint(link^.Node2) > Longint(node)) then
            begin
                x1 := node^.X;
                y1 := node^.Y;
                x2 := link^.Node2^.X;
                y2 := link^.Node2^.Y;
                dx := x2 - x1;
                dy := y2 - y1;
                dist := Sqrt((dx * dx) + (dy * dy));
                if (dist > 0) then
                begin
                    dx := Round(dx * RADIUS / dist);
                    dy := Round(dy * RADIUS / dist);

                    // Draw the link.
                    x1 := x1 + dx;
                    y1 := y1 + dy;
                    x2 := x2 - dx;
                    y2 := y2 - dy;
                    if (link^.InTree) then
                        Canvas.Pen.Width := 3
                    else
                        Canvas.Pen.Width := 1;
                    Canvas.MoveTo(x1, y1);
                    Canvas.LineTo(x2, y2);
                    Canvas.Pen.Width := 1;

                    // Draw the link cost.
                    x1 := (x1 + x2) div 2;
                    y1 := (y1 + y2) div 2;
                    Canvas.Brush.Color := Color;
                    Canvas.Pen.Color := Color;
                    Canvas.Ellipse(
                        x1 - RADIUS, y1 - RADIUS,
                        x1 + RADIUS, y1 + RADIUS);

                    txt := IntToStr(link^.Cost);
                    size := Canvas.TextExtent(txt);
                    Canvas.Pen.Color := clBlack;
                    Canvas.TextOut(
                        x1 - (size.cx div 2),
                        y1 - (size.cy div 2),
                        txt);
                end; // End if (dist > 0) then ...
            end; // End if (link^.Node2 > node) then ...

            // Go to the next link for this node.
            link := link^.NextLink;
        end; // End while (link <> nil) do ...

        if ((node = Node_1) or (node = Node_2) or
            ((Node_1 = nil) and (node = RootNode))) then
        begin
            // Highlight the node.
            Canvas.Brush.Color := clBlack;
            Canvas.Font.Color := clWhite;
        end else begin
            // Do not highlight the node.
            Canvas.Brush.Color := clWhite;
            Canvas.Font.Color := clBlack;
        end;

        // Draw the node.
        x1 := node^.X;
        y1 := node^.Y;
        Canvas.Ellipse(
            x1 - RADIUS, y1 - RADIUS,
            x1 + RADIUS, y1 + RADIUS);

        txt := IntToStr(node^.Id);
        size := Canvas.TextExtent(txt);
        Canvas.TextOut(
            x1 - (size.cx div 2),
            y1 - (size.cy div 2),
            txt);
        Canvas.Font.Color := clBlack;

        // Go to the next node.
        node := node^.NextNode;
    end; // End while (node <> nil) do ...

    Canvas.Brush.Color := Color;
    Canvas.Font.Color := clBlack;
end;

// Load the network data from a file with format:
//   # Nodes
//   For each node: Id, X, Y
// After Id, X, and Y for all nodes:
//   For each node: # Links, for each link:
//       Node2, Cost
procedure TPathSForm.LoadNetwork(fname : String);
var
    i, num_nodes, num_links, to_node : Integer;
    net_file                         : TextFile;
    node                             : PNode;
    link                             : PLink;
begin
    // Start a new network.
    NewNetwork;

    // Open the file.
    AssignFile(net_file, fname);
    Reset(net_file);

    // Read the number of nodes and links.
    Readln(net_file, num_nodes);

    // Read the nodes' Id, X, and Y.
    MaxId := 0;
    node := @NodeSentinel;
    for i := 1 to num_nodes do
    begin
        GetMem(node^.NextNode, SizeOf(TNode));
        node := node^.NextNode;
        with node^ do
        begin
            Readln(net_file, Id, X, Y);
            LinkSentinel.NextLink := nil;
            if (MaxId < Id) then MaxId := Id;
        end;
    end;
    node^.NextNode := nil;

    // Read the link information.
    node := NodeSentinel.NextNode;
    for i := 1 to num_nodes do
    begin
        node^.LinkSentinel.NextLink := nil;
        Readln(net_file, num_links);
        for i := 1 to num_links do
        begin
            GetMem(link, SizeOf(TLink));
            link^.NextLink := node^.LinkSentinel.NextLink;
            node^.LinkSentinel.NextLink := link;
            Readln(net_file, to_node, link^.Cost);
            link^.Node2 := FindNodeById(to_node);
            link^.Node1 := node;
        end;

        // Get the link info for the next node.
        node := node^.NextNode;
    end;

    // Close the file.
    CloseFile(net_file);
    ResetPathTree;

    // The network has not yet been modified.
    FileName := fname;
    Caption := 'PathS [' + fname + ']';
end;

// Find a node given its Id.
function TPathSForm.FindNodeById(id : Integer) : PNode;
var
    node : PNode;
begin
    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        if (node^.Id = id) then break;
        node := node^.NextNode;
    end;
    if (node <> nil) then
        Result := node
    else
        Result := nil;
end;

// Save the network data into a file with format:
//   # Nodes
//   For each node: Id, X, Y
// After Id, X, and Y for all nodes:
//   For each node: # Links, for each link:
//       Node2, Cost
procedure TPathSForm.SaveNetwork(fname : String);
var
    i        : Integer;
    net_file : TextFile;
    node     : PNode;
    link     : PLink;
begin
    // Open the file.
    AssignFile(net_file, fname);
    Rewrite(net_file);

    // Save the number of nodes.
    i := 0;
    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        i := i + 1;
        node := node^.NextNode;
    end;
    Writeln(net_file, i);

    // Save the node identifiers and coordinates.
    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        Writeln(net_file, node^.Id, ' ', node^.X, ' ', node^.Y);
        node := node^.NextNode;
    end;

    // Save the link information.
    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        // Count the links.
        i := 0;
        link := node^.LinkSentinel.NextLink;
        while (link <> nil) do
        begin
            i := i + 1;
            link := link^.NextLink;
        end;
        Writeln(net_file, i);

        // Save the link information.
        link := node^.LinkSentinel.NextLink;
        while (link <> nil) do
        begin
            Writeln(net_file, link^.Node2^.Id, ' ', link^.Cost);
            link := link^.NextLink;
        end;

        // Go to the next node.
        node := node^.NextNode;
    end;

    // Close the file.
    CloseFile(net_file);

    DataModified := False;
    FileName := fname;
    Caption := 'PathS [' + fname + ']';
end;

// Reset the edit mode.
procedure TPathSForm.ResetEditMode;
begin
    EditMode := emNone;
    Cursor := crDefault;
    Node_1 := nil;
    Node_2 := nil;
end;

// Perform the task appropriate for this edit mode.
procedure TPathSForm.FormMouseDown(Sender: TObject; Button: TMouseButton;
  Shift: TShiftState; X, Y: Integer);
begin
    case EditMode of
        emNone:
            FindPathTree(SelectNode(X, Y));
        emNewNode:
            begin
                CreateNode(X, Y);
                EditMode := emNone;
            end;
        emDeleteNode:
            begin
                DeleteNode((SelectNode(X, Y)));
                EditMode := emNone;
            end;
        emNewLink1:
            begin
                Node_1 := SelectNode(X, Y);
                if (Node_1 = nil) then
                    EditMode := emNone
                else
                    EditMode := emNewLink2;
            end;
        emNewLink2:
            begin
                Node_2 := SelectNode(X, Y);
                if (Node_2 <> nil) then CreateLink;
                EditMode := emNone;
            end;
        emDeleteLink1:
            begin
                Node_1 := SelectNode(X, Y);
                if (Node_1 = nil) then
                    EditMode := emNone
                else
                    EditMode := emDeleteLink2;
            end;
        emDeleteLink2:
            begin
                Node_2 := SelectNode(X, Y);
                if (Node_2 <> nil) then DeleteLink(Node_1, Node_2);
                EditMode := emNone;
            end;
    end; // End case EditMode of ...

    if (EditMode = emNone) then
    begin
        Cursor := crDefault;
        Node_1 := nil;
        Node_2 := nil;
    end;

    DrawNetwork;
end;

// Find the node that contains this point.
function TPathSForm.SelectNode(X, Y : Integer) : PNode;
var
    dx, dy, radius2 : Integer;
    node            : PNode;
begin
    radius2 := RADIUS * RADIUS;
    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        dx := node^.X - X;
        dy := node^.Y - Y;
        if ((dx * dx + dy * dy) <= radius2) then
        begin
            Result := node;
            exit;
        end;
        node := node^.NextNode;
    end;
    Result := nil;
end;

// Delete the node from the network.
procedure TPathSForm.DeleteNode(target : PNode);
var
    node, next_node : PNode;
begin
    if (target = nil) then exit;

    // Free the target's links.
    while (target^.LinkSentinel.NextLink <> nil) do
    begin
        DeleteLink(target,
            target^.LinkSentinel.NextLink^.Node2);
    end;

    // Find the target in the node list.
    node := @NodeSentinel;
    next_node := node^.NextNode;
    while (next_node <> nil) do
    begin
        if (next_node = target) then break;
        node := next_node;
        next_node := node^.NextNode;
    end;
    if (next_node = nil) then exit; // Not found.

    // Remove the node.
    node^.NextNode := target^.NextNode;
    FreeMem(target);

    // Redraw the network.
    ResetPathTree;
    DrawNetwork;

    // The data has been modified.
    DataModified := True;
    Caption := 'PathS*[' + FileName + ']';
end;

// Delete a link from the network.
procedure TPathSForm.DeleteLink(n1, n2 : PNode);
begin
    if ((n1 = nil) or (n2 = nil)) then exit;

    // Remove the link from the nodes' link lists.
    RemoveLinkFromNode(n1, n2);
    RemoveLinkFromNode(n2, n1);

    // Redraw the network.
    ResetPathTree;
    DrawNetwork;

    // The data has been modified.
    DataModified := True;
    Caption := 'PathS*[' + FileName + ']';
end;

// Remove the link to node n2 from node n1's Links array.
procedure TPathSForm.RemoveLinkFromNode(n1, n2 : PNode);
var
    link, next_link : PLink;
begin
    // Find the link.
    link := @n1^.LinkSentinel;
    next_link := link^.NextLink;
    while (next_link <> nil) do
    begin
        if (next_link^.Node2 = n2) then break;
        link := next_link;
        next_link := link^.NextLink;
    end;
    if (next_link = nil) then exit;

    // Remove the link.
    link^.NextLink := next_link^.NextLink;
    FreeMem(next_link);
end;

// Create a new node.
procedure TPathSForm.CreateNode(X, Y : Integer);
var
    node : PNode;
begin
    // Create the new node.
    GetMem(node, SizeOf(TNode));
    MaxId := MaxId + 1;
    node^.Id := MaxId;
    node^.X := X;
    node^.Y := Y;
    node^.LinkSentinel.NextLink := nil;

    // Add the node to the node list.
    node^.NextNode := NodeSentinel.NextNode;
    NodeSentinel.NextNode := node;

    // Redraw the network.
    ResetPathTree;
    DrawNetwork;

    // The data has been modified.
    DataModified := True;
    Caption := 'PathS*[' + FileName + ']';
end;

// Create a new link between nodes Node_1 and Node_2.
procedure TPathSForm.CreateLink;
var
    link1, link2 : PLink;
    txt          : String;
begin
    if ((Node_1 = nil) or (Node_2 = nil)) then exit;

    // Do not allow links from a node to itself.
    if (Node_1 = Node_2) then
    begin
        ShowMessage('You cannot make a link between a node and itself.');
        exit;
    end;

    // Get the link cost from the user.
    txt := InputBox('Link cost', 'Link Cost', '10');

    // Create the links.
    GetMem(link1, SizeOf(TLink));
    GetMem(link2, SizeOf(TLink));
    link1^.Cost := StrToInt(txt);
    link2^.Cost := link1^.Cost;
    link1^.Node1 := Node_1;
    link1^.Node2 := Node_2;
    link2^.Node1 := Node_2;
    link2^.Node2 := Node_1;
    link1^.NextLink := nil;
    link2^.NextLink := nil;

    // Add the links to the nodes' link lists.
    link1^.NextLink := Node_1^.LinkSentinel.NextLink;
    Node_1^.LinkSentinel.NextLink := link1;

    link2^.NextLink := Node_2^.LinkSentinel.NextLink;
    Node_2^.LinkSentinel.NextLink := link2;

    // Redraw the network.
    ResetPathTree;
    DrawNetwork;

    // The data has been modified.
    DataModified := True;
    Caption := 'PathS*[' + FileName + ']';
end;

// Find a shortest path tree rooted at this node using a
// label setting algorithm.
procedure TPathSForm.FindPathTree(root : PNode);
var
    candidate_sentinel  : TCandidate;
    new_candidate       : PCandidate;
    before, best_before : PCandidate;
    best_dist, new_dist : Integer;
    node, to_node       : PNode;
    link                : PLink;
begin
    if (root = nil) then exit;
    RootNode := root;

    // Reset the tree.
    ResetPathTree;

    // Start with the root in the shortest path tree.
    root^.Dist := 0;
    root^.InLink := nil;
    root^.Status := nsNowInList;
    GetMem(new_candidate, SizeOf(TCandidate));
    candidate_sentinel.NextCandidate := new_candidate;
    new_candidate^.NextCandidate := nil;
    new_candidate^.Node := root;

    // Repeat until the candidate list is empty.
    while (candidate_sentinel.NextCandidate <> nil) do
    begin
        // Find the candidate closest to the root.
        best_dist := INFINITY;
        best_before := nil;
        before := @candidate_sentinel;
        new_candidate := before^.NextCandidate;
        while (new_candidate <> nil) do
        begin
            new_dist := new_candidate^.Node^.Dist;
            if (new_dist < best_dist) then
            begin
                best_before := before;
                best_dist := new_dist;
            end;
            before := new_candidate;
            new_candidate := before^.NextCandidate;
        end;

        // Add this node to the shortest path tree.
        new_candidate := best_before^.NextCandidate;
        node := new_candidate^.Node;
        node^.Status := nsWasInList;

        // Remove the node from the candidate list.
        best_before^.NextCandidate :=
            new_candidate^.NextCandidate;
        FreeMem(new_candidate);

        // Examine the node's neighbors.
        link := node^.LinkSentinel.NextLink;
        while (link <> nil) do
        begin
            to_node := link^.Node2;
            // If the node hasn't been in the candidate
            // list, add it.
            if (to_node^.Status = nsNotInList) then
            begin
                // Update the node's status and distance.
                to_node^.Status := nsNowInList;
                to_node^.Dist := best_dist + link^.Cost;
                to_node^.InLink := link;

                // Add it to the list.
                GetMem(new_candidate, SizeOf(TCandidate));
                new_candidate^.Node := to_node;
                new_candidate^.NextCandidate :=
                    candidate_sentinel.NextCandidate;
                candidate_sentinel.NextCandidate :=
                    new_candidate;
            end else if (to_node^.Status = nsNowInList) then
            begin
                // If the node is now in the candidate list,
                // update its Dist and InLink values.
                new_dist := best_dist + link.Cost;
                if (new_dist < to_node.Dist) then
                begin
                    to_node.Dist := new_dist;
                    to_node.InLink := link;
                end;
            end;

            link := link^.NextLink;
        end; // End examining the node's neighbors.
    end; // End while (candidate list is not empty) ...

    // Mark the InLinks so they are easy to draw.
    to_node := NodeSentinel.NextNode;
    while (to_node <> nil) do
    begin
        link := to_node^.InLink; // The link into this node.
        if (link <> nil) then
        begin
            link.InTree := True;

            // Mark the reverse link.
            node := link^.Node1; // The link's start node.
            link := to_node^.LinkSentinel.NextLink;
            while (link <> nil) do
            begin
                if (link^.Node2 = node) then break;
                link := link^.NextLink;
            end;
            if (link <> nil) then link^.InTree := True;
        end;
        to_node := to_node^.NextNode;
    end;

    // Redraw the network.
    GotTree := True;
    DrawNetwork;
end;

// Remove all the links from the shortest path tree.
procedure TPathSForm.ResetPathTree;
var
    node : PNode;
    link : PLink;
begin
    GotTree := False;

    node := NodeSentinel.NextNode;
    while (node <> nil) do
    begin
        node^.Status := nsNotInList;
        node^.Dist   := INFINITY;
        node^.InLink := nil;
        link := node^.LinkSentinel.NextLink;
        while (link <> nil) do
        begin
            link^.InTree := False;
            link := link^.NextLink;
        end;
        node := node^.NextNode;
    end;
end;

end.
