A+ » VCE » Further Maths U3 & 4 Master Notes » OA2 Networks and Decision Mathematics » FM Dijkstra's Algorithm

FM Dijkstra's Algorithm

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