Network Algorithms: Least weight path between two vertices
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 realworld applications such as routing and navigation
Important Network Algorithms

The two algorithms for finding the least weight path are Dijkstra’s Algorithm and the FloydWarshall 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 FloydWarshall Algorithm finds the shortest paths between all pairs of vertices. It’s comparatively slower and complex but handles negative weights.
Process of Dijkstra’s Algorithm

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.
Application and Features of the FloydWarshall Algorithm

The FloydWarshall 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 FloydWarshall algorithm is able to do this for all pairs of vertices simultaneously, not just from a single source.

One limitation of the FloydWarshall 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.
Practicing and Understanding

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 stepbystep calculations can greatly increase understanding of these concepts.