How to calculate the shortest path in a graph

Calculating the shortest path in a graph depends on whether the graph is weighted or unweighted, directed or undirected, and whether there are negative weights. Let’s go step by step.

---

1️⃣ Unweighted Graph

If all edges have the same weight (or you just care about number of edges), use BFS.

BFS finds the minimum number of edges from the start node to every other node.

Algorithm (BFS-based)

from collections import deque

def shortest_path_unweighted(graph, start):
    visited = set([start])
    distance = {start: 0}  # distance from start node
    queue = deque([start])
   
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
   
    return distance

Time Complexity: O(V + E)

Works for undirected and directed graphs as long as edges are unweighted.

---

2️⃣ Weighted Graph (Positive Weights)

Use Dijkstra’s Algorithm for graphs with non-negative edge weights.

Finds the minimum sum of edge weights from start to all other nodes.

Dijkstra’s Algorithm (Adjacency List + Min Heap)

import heapq

def dijkstra(graph, start):
    # graph: node -> list of (neighbor, weight)
    heap = [(0, start)]       # (distance, node)
    distance = {node: float('inf') for node in graph}
    distance[start] = 0
   
    while heap:
        dist, node = heapq.heappop(heap)
        if dist > distance[node]:
            continue
        for neighbor, weight in graph[node]:
            if distance[node] + weight < distance[neighbor]:
                distance[neighbor] = distance[node] + weight
                heapq.heappush(heap, (distance[neighbor], neighbor))
   
    return distance

Time Complexity: O((V + E) log V) using min-heap

Handles directed/undirected graphs, positive weights only.

---

3️⃣ Weighted Graph (With Negative Edges)

Dijkstra cannot handle negative weights.

Use Bellman-Ford Algorithm instead:

Bellman-Ford Key Points

Relax all edges V-1 times (V = number of vertices).

Can detect negative cycles.

Time Complexity: O(V * E)

---

4️⃣ All-Pairs Shortest Path

If you need shortest paths between all pairs of nodes, use:

1. Floyd-Warshall Algorithm (Dynamic Programming)

Works for graphs with positive or negative weights (no negative cycles)

Time Complexity: O(V³)

2. Johnson’s Algorithm

Efficient for sparse graphs

Combines Dijkstra with reweighting

---

5️⃣ Key Notes / Summary

Graph Type Algorithm Notes

Unweighted BFS Distance = number of edges Weighted + positive edges Dijkstra Min-heap or priority queue Weighted + negative edges Bellman-Ford Can detect negative cycles All pairs Floyd-Warshall / Johnson DP or Dijkstra-based

---

🔹 Quick Analogy

BFS → “Step-count distance”

Dijkstra → “Minimum cost distance”

Bellman-Ford → “Minimum cost distance with possible debts (negative weights)”