Single-Destination Shortest Path

The single-destination shortest path problem aims to find the shortest path from every vertex in the graph to a given destination vertex. It allows reversing the perspective from the destination.

Algorithms like reverse Dijkstra and A* search can solve this on directed graphs with nonnegative weights.

Java - Reverse Dijkstra’s:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
void reverseDijkstra(Graph graph, int dest) {
  
  PriorityQueue<Vertex> pq = new PriorityQueue<>();
  pq.add(new Vertex(dest, 0));

  while (!pq.isEmpty()) {
    Vertex u = pq.poll();

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

C++ - A* search:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void astar(Graph graph, int dest) {

  auto cmp = [dest](const Vertex& a, const Vertex& b) {
    // Custom comparator 
  };

  priority_queue<Vertex, vector<Vertex>, decltype(cmp)> pq(cmp);

  // Initialize and add dest to pq

  while (!pq.empty()) {
    Vertex u = pq.top(); pq.pop();
    
    for (Vertex v : graph.inboundNeighbors(u)) {
      // Relaxation step
    }
  } 
}

Python - Reverse Dijkstra’s:

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

def reverse_dijkstra(graph, dest):

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

  while pq:
    dist, u = heapq.heappop(pq)
    if u in visited:  
      continue

    visited.add(u)

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

Useful for routing, transportation, and optimization problems where destination is fixed.

The Single-Destination Shortest Path problem aims to find the shortest paths from all vertices in a graph to a single destination vertex. It’s the reverse of the Single-Source Shortest Path problem. Dijkstra’s and Bellman-Ford algorithms can be modified for this by reversing the edges.

Algorithm

Initialization: Start with a destination vertex. Initialize distances to all vertices as infinite, except the destination vertex, which has a distance of zero.
Relaxation: Update the shortest path estimate if a shorter path is found.
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 SingleDestinationDijkstra {
    public static int[] dijkstra(int[][] graph, int destination) {
        int n = graph.length;
        int[] distance = new int[n];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[destination] = 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[v][u] != 0 && distance[u] + graph[v][u] < distance[v]) {
                    distance[v] = distance[u] + graph[v][u];
                }
            }
        }

        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 destination) {
    int n = graph.size();
    std::vector<int> distance(n, INT_MAX);
    distance[destination] = 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[v][u] && distance[u] + graph[v][u] < distance[v]) {
                distance[v] = distance[u] + graph[v][u];
            }
        }
    }
 
    return distance;
}

Python Code:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
def dijkstra(graph, destination):
    n = len(graph)
    distance = [float('inf')] * n
    distance[destination] = 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):
            if weight[u] and distance[u] + weight[u] < distance[v]:
                distance[v] = distance[u] + weight[u]

    return distance

The time complexity remains the same as the Single-Source Shortest Path problem. For Dijkstra’s, it’s (O(V^2)), and for Bellman-Ford, it’s (O(V \cdot E)).