Kth shortest path problem

Kth shortest path problem Description

Given a directed graph of N nodes (1, 2 … N) and M edges, find the the Kth shortest path from the starting point S to the ending point T. The path allows repeated passes through points or edges.

Note: Each shortest path must contain at least one edge.

Input format


The first line contains two integers N and M.

In the next M lines, each line contains three integers A, B, and L, indicating that there is a directed edge between point A and point B, and the length of the edge is L.

The last line contains three integers S, T and K, which respectively represent the starting point S, the ending point T and the Kth short path.

Output format

The output occupies one line and contains an integer indicating the length of the Kth short path. If the Kth short path does not exist, it outputs “-1”.

Data range

1≤ S,T ≤N≤ 10001 ≤S,T≤N ≤ 1000,
0≤ M ≤ 1050≤ M ≤10^5,
1≤ K ≤ 10001 ≤ K ≤1000,
1≤ L ≤100

Solution

A direct idea is to use the priority queue BFS. The priority queue (heap) stores some duals (x, dist), where x is the node number, and dist represents the distance from S along a certain path to x. At first, there was only (S, 0) in the heap. We continue to take the duals (x, dst) with the smallest dist value from the heap, and then expand along each edge (x, y) starting from x, and put the new duals (y, dist + length (x , Y) inserted into the heap (regardless of whether there is already a two-tuple node number y in the heap)

In the priority queue BFS(Dijkstra), when a state is taken out of the heap for the first time, the minimum cost from the initial state to it is obtained. Obvisouly, for any positive integer i and any node x, when the i-th tuple is taken from the heap containing the node x, the corresponding dist value is the t-th from S to x Short path. Therefore, when the expanded node y has been taken out K times, there is no need to insert it into the heap again. Finally, when the node T is taken out for the Kth time, a Kth short path from S to T is obtained. In the worst case, the priority queue BFS has a complexity of O (K * (N + M) * log (N + M). This problem gives the starting point and the ending point, and finds the shortest path (the least cost) path. Consider using A * algorithm to improve search efficiency

According to the design criteria of the evaluation function, the estimated distance f (x) from x to T in the Kth short path should not be greater than the actual distance g (x) from x to T in the Kth short path. Therefore, we can set the evaluation function f (x) as the shortest length from x to T, so that it can not only ensure that (x) ≤g (x), but also conform to the actual change trend of gx). In the end we got the following A * algorithm:

  1. Preprocess the shortest path length f (x) from each node x to the end point T-this is equivalent to solving the single-source shortest path problem starting from 7 on the reverse graph, whose time complexity is O (N + M) log (N + M ).
  2. Crate a binary heap and store some duals (x, dist + f(x), where x is the node number and dst shows the current distance traveled from S to x. At first there was only (S, 0 + f (0)) in the heap.
  3. Take the duals with the smallest dst + f (x) value (x, dst + f (x) from the binary heap, and then expand along each edge (xy) starting from x. If the node y is If the number of fetches has not reached K, the new binary (y, dst + length (xy) + f (y) is inserted into the heap.
  4. Repeat steps 2 to 3 until the Kth time to take out the duals containing the end point T, then the dist value in the duals is the Kth short path from S to T.

The upper bound of the complexity of the A * algorithm is the same as that of the priority queue BFS. However, because of the function of the valuation function, the number of visits of many nodes in the graph is far less than K, and the above A * algorithm has been able to find the results relatively quickly.

Java Code

import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

class Solution {
    int m, n, s, t, k;
    LinkedList<int[]>[] adj;
    LinkedList<int[]>[] adjRev;
    int[] dis;
    boolean[] visited;
    class dPair {
        int dis;
        int node;
        public dPair(int dis, int node) {
            this.dis = dis;
            this.node = node;
        }
    }

    class aPair{
        int fDis;//evaluated dis
        int rDis;//real dis
        int node;
        public aPair(int fDis, int rDis, int node) {
            this.fDis = fDis;
            this.rDis = rDis;
            this.node = node;
        }

    }
    public void solution(int n, int m, LinkedList<int[]>[] adj,LinkedList<int[]>[] adjRev, int s, int t, int k) {
        this.m = n;this.n = n;this.s = s;this.t = t; this.k = k;this.adj = adj;this.adjRev = adjRev;
        this.dis = new int[n+1];
        this.visited = new boolean[n+1];
        dijkstra();
        System.out.println(aStar());;
    }
    private void dijkstra(){
        PriorityQueue<dPair> pq = new PriorityQueue<>((a, b) -> (a.dis - b.dis));
        pq.offer(new dPair(0, t));
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[t] = 0;
        while (pq.size() > 0) {
            dPair cur = pq.poll();
            if (visited[cur.node]) continue;
            visited[cur.node] = true;
            //pay attention to direction!
            for (int[] x : adjRev[cur.node]) {
                if ( cur.dis + x[1] < dis[x[0]]) {
                    dis[x[0]] = cur.dis + x[1];
                    pq.offer(new dPair(dis[x[0]], x[0]));
                }
            }
        }
    }
    private int aStar() {
        PriorityQueue<aPair> pq = new PriorityQueue<>((a,b) -> a.fDis - b.fDis);
        pq.offer(new aPair(dis[s], 0, s));
        int count = 0;
        while (pq.size() > 0) {
            aPair cur = pq.poll();
            if (cur.node == t) {
                count++;
            }
            if (count == k) {
                return cur.rDis;
            }
            for (int[] x : adj[cur.node]) {
                pq.offer(new aPair(dis[x[0]] + cur.rDis + x[1],cur.rDis + x[1], x[0]));
            }

        }

        return -1;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        LinkedList<int[]>[] adj = new LinkedList[n+1];
        LinkedList<int[]>[] adjRev = new LinkedList[n+1];
        for (int i = 1; i <= n; i++) {
            adj[i] = new LinkedList();
            adjRev[i] = new LinkedList<>();
        }
        for (int i = 0; i < m; i++) {
            int x = cin.nextInt();
            int y = cin.nextInt();
            int z = cin.nextInt();
            adj[x].add(new int[]{y, z});
            adjRev[y].add(new int[]{x, z});
        }
        int s = cin.nextInt();
        int t = cin.nextInt();
        int k = cin.nextInt();
        if (s == t) {
            k++;
        }
        Solution obj = new Solution();
        obj.solution(n, m, adj, adjRev, s, t, k);
    }
}

Refrences:

  1. 算法竞赛进阶指南
  2. http://poj.org/problem?id=2449

Author: huadonghu

Leave a Reply

Your email address will not be published. Required fields are marked *