Network Algorithms: Least Weight Path Between Two Vertices

Core Concepts and Definition

A network is a graph in which each edge has a number associated with it, called the weight.
The least weight path between two vertices in a network is the path with the minimum total weight, that is, the path for which the sum of the weights of its edges is the smallest.
These paths are commonly used in real-world applications such as routing and navigation

The two algorithms for finding the least weight path are Dijkstra’s Algorithm and the Floyd-Warshall Algorithm.
Dijkstra’s Algorithm finds the shortest paths between the starting node and all other nodes in the graph. It does not work with graphs with negative weights.
The Floyd-Warshall Algorithm finds the shortest paths between all pairs of vertices. It’s comparatively slower and complex but handles negative weights.

Dijkstra’s Algorithm starts at the node that you choose (the “source node”) and it analyses the graph to find the shortest path between that node and all the other nodes in the graph.
The process uses a priority queue where vertices are organized according to their smallest tentative distance from the source.
The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.
Once the shortest path to the destination node is determined, the algorithm halts.

The Floyd-Warshall Algorithm is a different approach to the least weight path problem. It is used for finding the shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles).
It operates by using a matrix which records the lengths of shortest paths. It does this systematically by gradually improving an estimate of the shortest path between any two vertices.
The Floyd-Warshall algorithm is able to do this for all pairs of vertices simultaneously, not just from a single source.
One limitation of the Floyd-Warshall algorithm is that it does not return details of the paths themselves. To reconstruct the path, you would need to store this information separately during the algorithm.

The best way to understand these algorithms is to practice. Take a graph and manually execute these algorithms, then compare the results.
Visualising the network algorithm processes with diagrams and step-by-step calculations can greatly increase understanding of these concepts.