Single Source Shortest Path Algorithm

Introduction

The Single Source Shortest Path (SSSP) algorithm is a fundamental concept in graph theory and algorithms.

It aims to find the shortest path from a single source vertex to all other vertices in a graph.

The title of “father” of the Single Source Shortest Path (SSSP) algorithms is often attributed to Edsger W. Dijkstra in 1956.

Among several SSSP algorithms, Dijkstra’s algorithm and bellman ford algorithms are widely used for its efficiency and simplicity.

.

Notations

G – A graph
V – The set of vertices in G.
E – The set of edges in G.
w(u,v) – The weight or cost associated with the edge (u,v).
dist[v] – The distance from a designated source vertex s to vertex v.

.

Definition

The Single Source Shortest Path problem seeks to determine, for each vertex v in the graph G, the minimum distance dist[v] from a specified source vertex A.

The minimum distance is defined as the smallest sum of edge weights along a path from the source A to the vertex v among all possible paths.

.

Mathematical Representation

The objective is to find dist[v] for every v in set of vertices V such that

dist[v] = min(dist[u] + w(u,v))

where the minimum is taken over all vertices u in V, and w(u,v) represents the weight of the edge connecting u to v.

The solution to the SSSP problem provides a set of distances dist[v] that satisfies the minimization condition, revealing the shortest paths from the source vertex A to all other vertices in the graph.

The shortest distance between the vertex F with respect to A is 13.

.

SSSP Algorithm

1. Start at the source vertex.
2. Mark the distance to itself as 0 and all other vertices as infinity.
3. For the current vertex, consider all of its neighbours and calculate their tentative distances through the current vertex.
4. If the newly calculated tentative distance is less than the current assigned value, update the distance.
5. Mark the current vertex as visited.
6. Repeat steps 3-5 until all vertices are visited.

.

Types of Algorithms in SSSP

There are two algorithms, Dijkstra and Bellman ford.

.

1. Dijkstra’s algorithm – is a popular algorithm for solving the Single Source Shortest Path (SSSP) problem in a graph with non-negative edge weights. It efficiently finds the shortest paths from a specified source vertex to all other vertices in the graph. Dijkstra’s algorithm is widely used in various applications, such as network routing and navigation systems, where finding the shortest paths from a source to all destinations is crucial.
2. Bellman-Ford Algorithm – is another approach to solving the Single Source Shortest Path (SSSP) problem, but it can handle graphs with edges having negative weights.
   This algorithm is less efficient than Dijkstra’s algorithm but is more versatile in handling a wider range of graphs.
   Bellman-Ford is used in routing protocols like RIP (Routing Information Protocol), telecommunication network planning, resource management in cloud computing, game development, urban planning etc.

.

Applications of SSSP Algorithm

1. Negative Cycles – SSSP algorithms like Bellman-Ford can detect negative cycles in a graph. A negative cycle is a cycle where the sum of the edge weights is negative. Detecting negative cycles is crucial in scenarios like financial modelling, where it helps identify arbitrage opportunities.

2. Heuristic Approaches – In certain scenarios, heuristic approaches like A* search algorithm are used for pathfinding. These algorithms combine the benefits of informed search and heuristics to find efficient paths.

3. Parallelization – Parallel algorithms for SSSP, especially for large graphs, have been developed. These leverage parallel computing architectures to speed up the computation of shortest paths.

4. Applications Beyond Networks – While SSSP algorithms are commonly associated with network-related problems, they find applications in diverse fields such as biology (protein-protein interaction networks), transportation (finding optimal routes), and social network analysis.

5. Weighted vs. Unweighted Graphs – SSSP algorithms are designed for weighted graphs where edges have associated costs or distances. For unweighted graphs, simpler algorithms like Breadth-First Search (BFS) can be used to find shortest paths.

6. Dynamic Graphs – Handling dynamic graphs (graphs that change over time) is an active area of research. Algorithms must adapt to additions or deletions of edges or vertices.

7. Path Reconstruction – Some SSSP algorithms, like Dijkstra’s, can be modified to reconstruct the actual paths along with the shortest distances. This information is valuable in understanding the route taken.

8. Graph Theory Applications – SSSP algorithms contribute to solving problems in graph theory, where understanding the relationships and connectivity between vertices is fundamental.