Single-Source Shortest Path(SSSP) Problem in Python

The single-source shortest path problem is about finding the paths between a given vertex(called the source) to all the other vertices(called the destination) in a graph such that the total distance between them is minimum.

 There are classical sequential algorithms that solve this problem, such as Breadth-First Search(BFS) algorithm and Dijkstra’s algorithm. The SSSP problem finds its applications in several real-life problems.

For Example,

• There exists five offices in five different cities.
• The cost of travel between each pair of cities is known.
• We have to find the cheapest way between the head office and different branches in various cities.

The following algorithms can be utilized to solve the single-source shortest path algorithm:

• Breadth First Search Algorithm
• Dijkstra’s Algorithm
• Bellman Ford Algorithm

Creation of Graph

To implement the Graph data structure, we first initialize the “Graph” class. Then, we overwrite the __init__ function and create another function to add edges between the newly added nodes.

#Initializing the Graph Class
class Graph:
    def __init__(self, gdict=None):
        if gdict is None:
            gdict = {}
        self.gdict = gdict
    
    def addEdge(self, vertex, edge):
        self.gdict[vertex].append(edge)

Breadth First Search for SSSP

The Breadth-First Search(BFS) technique starts at some arbitrary node of a graph and checks adjacent nodes at the current level. This way, all the unvisited nodes of the same level are traversed before moving on to the next level of the graph.

For the implementation of SSSP using the BFS algorithm, we simply traverse from the source node to the destination node along the BFS path.

Implementation of BFS Traversal for SSSP

The BFS Traversal algorithm for SSSP is based on the following steps:

• Insert the graph’s source vertex at the back of a queue.
• Retrieve the first item of the queue and mark it as visited.
• Created a list of the nodes adjacent to the current node. Traverse the unvisited nodes and insert them to the back of queue.
• Repeat the steps continuously until the queue is empty or the destination node is reached.

#Function to implement BFS Traversal for SSSP
def bfs(self, start, end):
    queue = []
    queue.append([start])
    while queue:
        path = queue.pop(0)
        node = path[-1]
        if node == end:
            return path
        for adjacent in self.gdict.get(node, []):
            new_path = list(path)
            new_path.append(adjacent)
            queue.append(new_path)

customDict = { "a" : ["b", "c"],
               "b" : ["d", "g"],
               "c" : ["d", "e"],
               "d" : ["f"],
               "e" : ["f"],
               "g" : ["f"]
            }

g = Graph(customDict)
print(g.bfs("a", "e"))

#Output
['a', 'c', 'e']

Time and Space Complexity

The time complexity of BFS for the SSSP Problem is O(V+E) where “V” and “E” denote the number of vertices and edges respectively. The space complexity is O(V+E) as well since we need to enqueue and dequeue all the elements of the graph in our queue.