Least weight path between two vertices

The Concept of Least Weight Path Between Two Vertices

  • Also known as shortest path, it relates to finding the path between two vertices such that the sum of weights of its constituent edges is minimised.
  • This concept is applicable in various fields including telecommunications, transportation, and data network routing.
  • The weight of a path is determined by the sum of the weights of the edges that make up the path.

Algorithms for Finding the Least Weight Path

  • Dijkstra’s Algorithm is a popular technique used to find the shortest path between vertices in a graph.
  • The other widely used algorithm is Bellman-Ford Algorithm, especially useful for graphs containing negative weight edges.
  • Floyd-Warshall Algorithm is also used when we want to find the shortest path between all pairs of vertices.

Dijkstra’s Algorithm

  • Dijkstra’s algorithm operates by visiting vertices in the graph starting with the object’s starting vertex.
  • It selects the unvisited vertex with the lowest-distance, calculates the distance through it to each unvisited neighbour, and updates the neighbour’s distance if smaller.
  • It was conceived by computer scientist Edsger W. Dijkstra in 1956.

Bellman-Ford Algorithm

  • Can handle graphs where some of the edge weights are negative.
  • Bellman-Ford algorithm executes progressively according to the ‘principle of relaxation’.
  • Relaxation is the process of replacing the distance of a node with the shortest distance.

Floyd-Warshall Algorithm

  • A different type of algorithm that solves the all pairs shortest path problem.
  • Floyd-Warshall algorithm’s time complexity is O(V^3), where V is the number of vertices in the graph.
  • It achieves this by incrementally improving an estimate on the shortest path between two vertices.

Common Pitfalls and Errors

  • Beware of negative cycles, it makes finding the shortest path impossible in some cases.
  • Not all algorithms work accurately if you have negative edge weights in your graph.
  • Be diligent about declaring and updating your visited and unvisited vertices in order to prevent infinite loops.

Practical Application and Exercises

  • Use real-life situations (map routing problems, flight itinerary planning) to create and solve least weight path problems.
  • Hands-on coding exercises using algorithms like Dijkstra’s, Bellman-Ford, and Floyd-Warshall can substantially improve understanding.