Shortest Path

   {  Exmpl5.3-4_ShortestPath.mpl  }

   {  H.P. Williams, Model Building in Mathematical Programming, 3rd ed.  }

   {  Chapter 5.3,  Example 4,  Shortest Path,  Size: 9x16,  Page 90  }


TITLE
    ShortestPath;

INDEX
    node      := 0..8;

    FromNode  := node;
    ToNode    := node;

DATA
    PathDist[FromNode,ToNode] := [ 0, 1,  1,
                                   0, 3,  1,
                                   1, 2,  1,
                                   1, 3,  2,
                                   2, 3,  1,
                                   2, 4,  1,
                                   2, 5,  3,
                                   3, 4,  2,
                                   3, 6,  4,
                                   4, 5,  3,
                                   4, 6,  2,
                                   4, 7,  4,
                                   5, 7,  1,
                                   6, 7,  2,
                                   6, 8,  1,
                                   7, 8,  1];

    StartPath[node] := [0, 1];

    EndPath[node] := [8, 1];

VARIABLES
    Path[FromNode,ToNode] -> x
        WHERE (PathDist);

MODEL

    MIN TotalDistance = SUM(FromNode, ToNode: PathDist * Path);

SUBJECT TO

    FlowBalance[node]:

        SUM(FromNode: Path[FromNode,ToNode:=node]) + StartPath
      =
        SUM(ToNode: Path[FromNode:=node,ToNode]) + EndPath;

END