Shortest Path Algorithms: Dijkstra & Bellman-Ford

Dijkstra's Algorithm

Dijkstra’s algorithm finds the shortest path from a single source vertex to all other vertices in a weighted graph with non-negative weights.

How It Works

• Start with the source vertex, assign initial distances: 0 for the source and infinity for others.
• Select the unvisited vertex with the smallest tentative distance.
• Update neighbors' distances if shorter paths are found via the current vertex.
• Mark the current vertex as visited and repeat until all vertices are visited.

Python Code Example

import heapq

def dijkstra(graph, start):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[start] = 0
    priority_queue = [(0, start)]

    while priority_queue:
        current_distance, current_vertex = heapq.heappop(priority_queue)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))

    return distances

# Usage example
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 3, 'D': 2, 'E': 3},
    'C': {'B': 1, 'D': 4, 'E': 5},
    'D': {},
    'E': {'D': 1}
}

distances = dijkstra(graph, 'A')
print(distances)

Bellman-Ford Algorithm

Bellman-Ford algorithm finds the shortest paths from a single source vertex to all other vertices in a graph, and it can handle graphs with some edges having negative weights.

How It Works

• Initialize distances from source to all vertices as infinity, except source which is 0.
• Relax all edges V-1 times (V = number of vertices).
• Check for negative weight cycles (if further relaxation is possible, negative cycle exists).

Python Code Example

def bellman_ford(graph, start):
    distance = {vertex: float('infinity') for vertex in graph}
    distance[start] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if distance[vertex] + weight < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + weight

    # Check for negative weight cycles
    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if distance[vertex] + weight < distance[neighbor]:
                raise ValueError("Graph contains a negative weight cycle")

    return distance

# Usage example
graph = {
    'A': {'B': -1, 'C': 4},
    'B': {'C': 3, 'D': 2, 'E': 2},
    'C': {},
    'D': {'B': 1, 'C': 5},
    'E': {'D': -3}
}

distances = bellman_ford(graph, 'A')
print(distances)

Key Differences

• Dijkstra works only with non-negative edge weights; Bellman-Ford works with negative weights but no negative cycles.
• Dijkstra is generally faster (using priority queues), Bellman-Ford is simpler but slower.
• Both algorithms solve the single-source shortest path problem.

Applications

• Network routing protocols.
• Optimal pathfinding in maps and games.
• Detecting negative cycles in financial models.