MPL Model Library MPL Model Library



Shortest Path, Example 9.3-1, Hillier and Lieberman

   {  Exmpl_9.3-1_ShortestPath.mpl  }

   {  Hillier and Lieberman, Introduction to Operations Research, 7th ed.  }

   {  Chapter 9.3,  Example 1, Shortest path,  Size: 7x12,  Page 411  }

TITLE
    ShortestPath;

INDEX
    node := (O, A, B, C, D, E, T);
   
    FromNode := node;
    ToNode   := node;

DATA
    Distance[FromNode, ToNode] :=

       [O,  A,  2,
        O,  B,  5,
        O,  C,  4,
        A,  B,  2,
        A,  D,  7,
        B,  C,  1,
        B,  D,  4,
        B,  E,  3,
        C,  E,  4, 
        D,  E,  1,
        D,  T,  5,
        E,  T,  7];


VARIABLES
    Path[FromNode, ToNode] WHERE (Distance > 0);

MODEL

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

SUBJECT TO

    FlowBalance[node] :

         1 IF (node=O) + SUM(FromNode: Path[FromNode, ToNode:=node]) 
      =        
         1 IF (node=T) + SUM(ToNode: Path[FromNode:=node, ToNode]);

END



Return to MPL Model Library