Single-Source Shortest Path

The single-source shortest path problem aims to find the shortest path from a source vertex to every other vertex in the graph. Algorithms like Dijkstra’s and Bellman-Ford can solve this for directed graphs with nonnegative edge weights.

Java - Dijkstra’s algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// Dijkstra's algorithm
void dijkstra(Graph graph, int source) {

  PriorityQueue<Vertex> pq = new PriorityQueue<>(); 
  pq.add(new Vertex(source, 0));
  
  while (!pq.isEmpty()) {
    Vertex u = pq.poll();

    for (Vertex v : graph.neighbors(u)) {
      int dist = u.dist + graph.weight(u, v);
      if (dist < v.dist) {
        v.dist = dist;
        pq.add(v); 
      }
    }
  }
}

C++ - Bellman-Ford algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

// Bellman-Ford algorithm  
void bellmanFord(Graph graph, int source) {

  // Initialize  
  for (auto &vertex : graph.vertices) {
    vertex.dist = INF;
  }

  source.dist = 0;

  // Relax edges  
  for (int i = 0; i < graph.V; i++) {
    for (auto &edge : graph.edges) {
      // Relax edge
    }
  }

}

Python - Dijkstra’s algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

import heapq

# Dijkstra's algorithm
def dijkstra(graph, source):

  pq = [(0, source)]
  visited = set()
  
  while pq:
    dist, u = heapq.heappop(pq)
    if u in visited:
      continue

    visited.add(u)

    for v, weight in graph[u]:
      if v not in visited:
        heapq.heappush(pq, (dist + weight, v))

Enables finding shortest paths from a given start vertex useful for network routing, pathfinding, and graph analysis.

The Single-Source Shortest Path problem aims to find the shortest paths from a source vertex to all other vertices in a weighted graph. Algorithms like Dijkstra’s and Bellman-Ford are commonly used for this.

Algorithm

  1. Initialization: Start with a source vertex. Initialize distances to all vertices as infinite, except the source vertex, which has a distance of zero.
  2. Relaxation: Update the shortest path estimate if a shorter path is found.
  3. Iteration: Repeat the relaxation step for all edges until no further updates are possible.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.Arrays;

public class Dijkstra {
    public static int[] dijkstra(int[][] graph, int start) {
        int n = graph.length;
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;

        boolean[] visited = new boolean[n];

        for (int i = 0; i < n; i++) {
            int u = -1;

            for (int j = 0; j < n; j++) {
                if (!visited[j] && (u == -1 || distance[j] < distance[u])) {
                    u = j;
                }
            }

            visited[u] = true;

            for (int v = 0; v < n; v++) {
                if (graph[u][v] != 0 && distance[u] + graph[u][v] < distance[v]) {
                    distance[v] = distance[u] + graph[u][v];
                }
            }
        }

        return distance;
    }
}

C++ Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

#include <vector>
#include <limits.h>

std::vector<int> dijkstra(std::vector<std::vector<int>> graph, int start) {
    int n = graph.size();
    std::vector<int> distance(n, INT_MAX);
    distance[start] = 0;

    std::vector<bool> visited(n, false);

    for (int i = 0; i < n; i++) {
        int u = -1;

        for (int j = 0; j < n; j++) {
            if (!visited[j] && (u == -1 || distance[j] < distance[u])) {
                u = j;
            }
        }

        visited[u] = true;

        for (int v = 0; v < n; v++) {
            if (graph[u][v] && distance[u] + graph[u][v] < distance[v]) {
                distance[v] = distance[u] + graph[u][v];
            }
        }
    }

    return distance;
}

Python Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def dijkstra(graph, start):
    n = len(graph)
    distance = [float('inf')] * n
    distance[start] = 0

    visited = [False] * n

    for _ in range(n):
        u = min((val, idx) for idx, val in enumerate(distance) if not visited[idx])[1]

        visited[u] = True

        for v, weight in enumerate(graph[u]):
            if weight and distance[u] + weight < distance[v]:
                distance[v] = distance[u] + weight

    return distance

Time complexity for Dijkstra’s algorithm is (O(V^2)) but can be improved to (O(E + V \log V)) with a priority queue. For Bellman-Ford, it is (O(V \cdot E)).