A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Shortest Path Problems

FM Shortest Path Problems

5.2 Introduction to Dijkstra’s Algorithm

Dijkstra’s Algorithm

  • Dijkstra’s algorithm provides a methodical method for determining the shortest path between two vertices.
  • Dijkstra’s algorithm works as follows:

1.  Construct a table consisting of a row of empty elements where each column corresponds to each vertex in the network except the starting vertex, and the first (and for now only) row corresponds to the starting vertex.

2.  In each element of the row, write the weight of the edge connecting the starting vertex to the vertex of the corresponding column. If there is no edge such edge for a vertex, place a cross in that element instead.

3.  Draw a square around the lowest weight in the row.

Read More »5.2 Introduction to Dijkstra’s Algorithm

5.1 Shortest Path by Inspection

Shortest Path Problems

  • In many cases it may be useful to determine the shortest path between two vertices of a graph. For example, for a graph representing the road network interconnecting several towns, we may want to find the fastest way of getting from one town to another.
  • The shortest path between two vertices is the path with the least weight.
  • The weight of a path is found by summing the weights of each edge making up that path.

Shortest Path by Inspection

  • Finding the shortest path via inspection involves a crude trial and error approach whereby multiple possible paths are tested until the shortest is found.
Read More »5.1 Shortest Path by Inspection