01-14 Minimum Distance

Implementing Dijkstra’s algorithm to find the minimum cost path from a starting vertex.

Test cases:

  • Example 1 (6 vertices) Shortest distance from 0 to 5 is 50.

  • Example 2 (10 vertices) Shortest distance from 0 to 9 is 80.

  • Example 3 (20 vertices) Shortest distance from 0 to 12 is 47. From 0 to 16 is 226.

  • Example 4 (200 vertices) Shortest distance from 0 to 36 is 77. From 0 to 191 is 101.

  • Example 5 (2000 vertices) Distances from 0:

      distanceTo[1117]=217
  distanceTo[1646]=203
  distanceTo[1732]=229

    The longest “shortest distance path” from vertex 0 is to vertex 658 and the distance is 306. The path itself is:

      [   0, 1697,  803, 1699,  708, 1420, 427,  574, 1534, 1955, 
   1954,  405, 1532, 1724, 1758, 1913, 658]