# 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.