Shortest-Path Problems

Definition

The shortest-path problem is a fundamental problem in graph theory that seeks to find the path with the minimum total weight (or cost) between two vertices in a graph.

There are variations of this problem, including:

• Single-source shortest paths: Finding the shortest paths from a single source vertex to all other vertices in the graph.
• Single-destination shortest paths: Finding the shortest paths from all vertices in the graph to a single destination vertex.
• All-pairs shortest paths: Finding the shortest paths between every pair of vertices in the graph.

Dijkstra's Algorithm

Dijkstra's Algorithm is a classic algorithm for solving the single-source shortest-path problem in a weighted graph where all edge weights are non-negative. It is a greedy algorithm that works by iteratively exploring the graph, maintaining a set of visited vertices and a set of unvisited vertices and updating the estimated shortest distance from the source to each vertex.

import heapq
 
def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
 
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
 
        if current_distance > distances[current_node]:
            continue
 
        for neighbor, weight in graph[current_node].items():
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
 
    return distances
 
if __name__ == '__main__':
    graph = {
        'A': {'B': 1, 'C': 4},
        'B': {'A': 1, 'D': 5, 'E': 1},
        'C': {'A': 4, 'F': 2},
        'D': {'B': 5, 'E': 2},
        'E': {'B': 1, 'D': 2, 'F': 3},
        'F': {'C': 2, 'E': 3}
    }
    
    start_node = 'A'
    shortest_distances = dijkstra(graph, start_node)
    print(f"Shortest distances from {start_node}: {shortest_distances}")
 

Warning

Dijkstra's Algorithm finds the shortest path only if all edge weights are non-negative.

Floyd's Algorithm

Floyd's algorithm, also known as the Floyd-Warshall algorithm, is a dynamic programming algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. Unlike Dijkstra's algorithm, which computes the shortest paths from a single source vertex, Floyd's algorithm calculates the shortest paths between every possible source-destination pair.

def floyd_warshall(graph):
    num_vertices = len(graph)
    # Initialize distance matrix
    dist = [[float('inf') for _ in range(num_vertices)] for _ in range(num_vertices)]
    
    for i in range(num_vertices):
        dist[i][i] = 0  # Distance to itself is 0
        for j in range(num_vertices):
           if graph[i].get(j) != None:
              dist[i][j] = graph[i][j]
 
    # Iterate through all vertices as intermediate nodes
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist
 
if __name__ == '__main__':
    graph = {
        0: {1: 5, 2: 1},
        1: {0: 5, 2: 2 , 3: 1},
        2: {0: 1, 1: 2, 3: 4},
		3: {1: 1, 2: 4}
    }
 
 
    shortest_distances = floyd_warshall(graph)
    print("Shortest distances between all pairs:")
    for row in shortest_distances:
        print(row)
 

Note

Floyd's algorithm can handle graphs with negative edge weights but does not work if there are negative cycles (a cycle where the sum of edge weights is negative), as shortest paths would be undefined in that case.