Single-Pair Shortest-Path Problem

The single-pair shortest path problem aims to find the shortest path between a given source and destination vertex in a graph. This is a special case of the single-source problem.

Some key algorithms are:

  • Breadth-first search
  • Dijkstra’s algorithm
  • A* search

Java - BFS:

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

boolean bfs(Graph graph, int src, int dest) {
  
  Queue<Vertex> queue = new LinkedList<>();
  queue.add(src);

  while (!queue.isEmpty()) {
    Vertex u = queue.remove();
    if (u == dest) return true;

    for (Vertex v : graph.neighbors(u)) {
      queue.add(v); 
    }
  }

  return false;
}

C++ - Dijkstra:

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

int dijkstra(Graph graph, int src, int dest) {
  
  // Min heap 
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;

  pq.push({0, src});

  while (!pq.empty()) {
    auto [dist, u] = pq.top(); 
    pq.pop();

    if (u == dest) {
      return dist; 
    }

    // Enqueue neighbors
  }

  return -1; // No path
}

Python - A* search:

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

import heapq

def astar(graph, src, dest):

  visited = set()
  pq = [(0, src)]

  while pq:
    cost, u = heapq.heappop(pq)
    if u in visited:
      continue
    
    visited.add(u)  
    if u == dest:  
      return cost

    for v, c in graph[u]:
      heapq.heappush(pq, (cost + c + heuristic(v), v))

  return -1 # No path

Computing single-pair shortest path is a key primitive in navigation systems and pathfinding.

The Single-Pair Shortest-Path problem seeks the shortest path between a given source vertex and a given destination vertex in a weighted graph. This is essentially a specialized version of the Single-Source Shortest-Path problem, where the goal is to find the shortest paths from one vertex to all other vertices. Algorithms like Dijkstra’s or Bellman-Ford can be used to solve this problem.

Algorithm

  1. Initialization: Initialize the distance to all vertices as infinite, except for the source vertex, which has a distance of zero.
  2. Relaxation: Update the shortest path estimate if a shorter path is found.
  3. Iteration: Continue the relaxation step for all edges until the destination vertex is reached or 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

import java.util.Arrays;

public class SinglePairShortestPath {
    public static int dijkstra(int[][] graph, int source, int destination) {
        int n = graph.length;
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[source] = 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;
            if (u == destination) return distance[u];
            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 -1;  // If destination is not reachable
    }
}

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

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

int dijkstra(std::vector<std::vector<int>> graph, int source, int destination) {
    int n = graph.size();
    std::vector<int> distance(n, INT_MAX);
    distance[source] = 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;
        if (u == destination) return distance[u];
        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 -1;  // If destination is not reachable
}

Python Code:

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

def dijkstra(graph, source, destination):
    n = len(graph)
    distance = [float('inf')] * n
    distance[source] = 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
        if u == destination:
            return distance[u]

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

    return -1  # If destination is not reachable

The time complexity is (O(V^2)) for Dijkstra’s algorithm. You can also use priority queues to improve it to (O(V + E \log V)).