Introduction
Shortest path problem
A network, is defined by two sets of symbols: nodes and arcs. An arc consists of an ordered pair of vertices and represents a possible direction of motion that may occur between vertices. Such a path is a chain in which the terminal node of each arc is defined to the initial node of the next arc. The problem of finding the shortest path (path of minimum length) from node 1 to any other node in a network is called a Shortest Path Problem.
Thus the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
To illustrate the Shortest Path Problem, we will thoroughly solve and discuss an example problem, Student's Night Out. In the example the shortest path between nodes is analogous to the problem of finding the shortest path between two venues on a map: the graph's vertices correspond to restaurants/pubs and the arcs correspond to road segments, each weighted by the length of its road segment.
Thus the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
To illustrate the Shortest Path Problem, we will thoroughly solve and discuss an example problem, Student's Night Out. In the example the shortest path between nodes is analogous to the problem of finding the shortest path between two venues on a map: the graph's vertices correspond to restaurants/pubs and the arcs correspond to road segments, each weighted by the length of its road segment.
Student's night out
After a long and daunting Engineering week a first year student wants to socialize in town before heading home. The student is unfamiliar with the scene and decides to plan his night using his knowledge of Operations Research. His objective is finding the shortest path between the Engineering Building and Springbok’s Pub (where every good night out apparently ends).
Starting the night he first wants to sit down for dinner at one of the following three places: Slug & Lettuce, Sgt Pepper or The Brazen Head.
Next he wants to have a few drinks at either Bohemia, Cubanna, De Akker or Aandklas where he can just sit and relax. He predicts that after drinks he would have enough courage to go dancing at Tollies or Nu’bar. After a good dance session he wants to grab a midnight snack at Mac Donald’s, Caltex or the Golden Tuckshop before heading to Springbok’s.
While he was researching Stellenbosch nightlife he acquired the following information restricting his route.
People that go to Slug & Lettuce do not go to Aandklas;
people that go to Sgt Pepper do not go to Bohemia or De Akker;
people that go to Brazen Head do not go to Cubana;
people that go to Bohemia or Aanklas do not go to Nu’bar;
people that go to Cubanna do not go to Tollies and
people that go to Nu’bar will not set foot in the Golden Tuckshop.
Using the Shortest Path Algorithm the student wants to find the shortest route from the Engineering faculty to Springbok's Pub while adhering to the constrains he encountered.
Starting the night he first wants to sit down for dinner at one of the following three places: Slug & Lettuce, Sgt Pepper or The Brazen Head.
Next he wants to have a few drinks at either Bohemia, Cubanna, De Akker or Aandklas where he can just sit and relax. He predicts that after drinks he would have enough courage to go dancing at Tollies or Nu’bar. After a good dance session he wants to grab a midnight snack at Mac Donald’s, Caltex or the Golden Tuckshop before heading to Springbok’s.
While he was researching Stellenbosch nightlife he acquired the following information restricting his route.
People that go to Slug & Lettuce do not go to Aandklas;
people that go to Sgt Pepper do not go to Bohemia or De Akker;
people that go to Brazen Head do not go to Cubana;
people that go to Bohemia or Aanklas do not go to Nu’bar;
people that go to Cubanna do not go to Tollies and
people that go to Nu’bar will not set foot in the Golden Tuckshop.
Using the Shortest Path Algorithm the student wants to find the shortest route from the Engineering faculty to Springbok's Pub while adhering to the constrains he encountered.
Network for minimizing path distance