I will be covering two types of path here. Lets' start!

Single Source Shortest Path

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

Single Source Shortest Path Problem (SSSPP)

Now, let's look at a real life problem :

• Five offices in different cities.

• Travel costs between these cities are known

• Find the cheapest way from head office to branches in different cities

Our problem is we need to find the cheapest flight from London to other cities. There are three ways to solve the problem.

• BFS

• Dijkstra's Algorithm

• Bellman Ford

BFS for SSSPP

We need to keep track of parent nodes of existing vertex.

class Graph: 
    def __init__(self, gdict = None): 
        if gdict is None: 
            gdict = {} 
        self.gdict = gdict
    def bfs(self, start, end): 
        queue = []  #O(1)
        queue.append([start]) 
        while queue: #O(V)
            path = queue.pop(0)
            node = path[-1] #O(1)
            if node == end: 
                return path
            for adjacent in self.gdict.get(node, []): #O(E)
                new_path = list(path) 
                new_path.append(adjacent) #O(1)
                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"))

Time complexity: O(E), Space complexity: O(E)

Why does BFS not work with weighted Graph?

BFS doesn't work for weighted graphs because it ignores edge weights. It assumes all edges have the same weight (implicitly 1). In a weighted graph, BFS might incorrectly find a longer path as the shortest path if it reaches a node earlier with a higher cumulative weight. For weighted graphs, algorithms like Dijkstra's are needed to handle varying edge weights.

For example, BFS would suggest A → C as the shortest path with a weight of 4. But the correct shortest path from A to C is A → B → C with a total weight of 2 (1+1).

BFS fails here because it doesn't consider edge weights.

Why Does DFS not work for SSSP?

DFS might report A → D → C with a total weight of 11, missing the shorter path A → B → C with a total weight of 2.

DFS doesn't care about shorter paths and can end up traversing much longer routes. That's how it often misses shortest path.

---

All Pairs Shortest Path

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

On the other hand, All pair shortest path problem is about finding a path between every vertex to all other vertices in a graph such that the total distance between them (source and destination) is minimum.

[ Further information will be update here ]

End