无人机物流网络最优路径规划

题目分析

给定 $n$ 个配送站和 $m$ 条双向空中走廊（每条有固定能耗），求从起点站 $s$ 到终点站 $t$ 的最小总能耗，以及从 $s$ 出发、位于某条最短路径上的所有"下一跳"站点（升序输出）。

特殊情况： $s = t$ 时输出 0 和 -1；不可达时两行都输出 -1。

思路

双向 Dijkstra + 最短路径判定

从 $s$ 跑 Dijkstra，得到 $\text{ds}[v]$ ： $s$ 到每个点的最短距离。
从 $t$ 跑 Dijkstra，得到 $\text{dt}[v]$ ： $t$ 到每个点的最短距离。
最小总能耗即 $\text{ds}[t]$ 。
判定下一跳：对于 $s$ 的每条邻边 $(s, v, w)$ ，如果 $w + \text{dt}[v] = \text{ds}[t]$ ，说明经过 $v$ 可以到达 $t$ 且总代价最优，则 $v$ 是合法的下一跳站点。

为什么这样判定？ $s \to v$ 的代价为 $w$ ， $v \to t$ 的最短代价为 $\text{dt}[v]$ ，两者之和等于全局最短路 $\text{ds}[t]$ ，说明 $s \to v \to \cdots \to t$ 构成一条最短路径。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,int> pli;

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<vector<pair<int,int>>> g(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    int s, t;
    scanf("%d%d", &s, &t);

    if (s == t) {
        printf("0\n-1\n");
        return 0;
    }

    const ll INF = 1e18;
    auto dijkstra = [&](int src) -> vector<ll> {
        vector<ll> dist(n + 1, INF);
        dist[src] = 0;
        priority_queue<pli, vector<pli>, greater<pli>> pq;
        pq.push({0, src});
        while (!pq.empty()) {
            auto [d, u] = pq.top(); pq.pop();
            if (d > dist[u]) continue;
            for (auto [v, w] : g[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist;
    };

    auto ds = dijkstra(s);
    auto dt = dijkstra(t);

    if (ds[t] >= INF) {
        printf("-1\n-1\n");
        return 0;
    }

    printf("%lld\n", ds[t]);

    vector<int> nexthops;
    for (auto [v, w] : g[s]) {
        if (ds[s] + w + dt[v] == ds[t]) {
            nexthops.push_back(v);
        }
    }
    sort(nexthops.begin(), nexthops.end());
    nexthops.erase(unique(nexthops.begin(), nexthops.end()), nexthops.end());

    if (nexthops.empty()) {
        printf("-1\n");
    } else {
        for (int i = 0; i < (int)nexthops.size(); i++) {
            if (i) printf(" ");
            printf("%d", nexthops[i]);
        }
        printf("\n");
    }
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        List<int[]>[] g = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) g[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt(), v = sc.nextInt(), w = sc.nextInt();
            g[u].add(new int[]{v, w});
            g[v].add(new int[]{u, w});
        }
        int s = sc.nextInt(), t = sc.nextInt();

        if (s == t) {
            System.out.println(0);
            System.out.println(-1);
            return;
        }

        long INF = (long) 1e18;
        long[] ds = dijkstra(g, s, n, INF);
        long[] dt = dijkstra(g, t, n, INF);

        if (ds[t] >= INF) {
            System.out.println(-1);
            System.out.println(-1);
            return;
        }

        System.out.println(ds[t]);

        TreeSet<Integer> nexthops = new TreeSet<>();
        for (int[] e : g[s]) {
            int v = e[0], w = e[1];
            if (ds[s] + w + dt[v] == ds[t]) {
                nexthops.add(v);
            }
        }

        if (nexthops.isEmpty()) {
            System.out.println(-1);
        } else {
            StringBuilder sb = new StringBuilder();
            for (int v : nexthops) {
                if (sb.length() > 0) sb.append(' ');
                sb.append(v);
            }
            System.out.println(sb);
        }
    }

    static long[] dijkstra(List<int[]>[] g, int src, int n, long INF) {
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[src] = 0;
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, src});
        while (!pq.isEmpty()) {
            long[] top = pq.poll();
            long d = top[0];
            int u = (int) top[1];
            if (d > dist[u]) continue;
            for (int[] e : g[u]) {
                int v = e[0], w = e[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

import heapq
import sys
input = sys.stdin.readline

def dijkstra(g, src, n):
    INF = float('inf')
    dist = [INF] * (n + 1)
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in g[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def main():
    n, m = map(int, input().split())
    g = [[] for _ in range(n + 1)]
    for _ in range(m):
        u, v, w = map(int, input().split())
        g[u].append((v, w))
        g[v].append((u, w))
    s, t = map(int, input().split())

    if s == t:
        print(0)
        print(-1)
        return

    ds = dijkstra(g, s, n)
    dt = dijkstra(g, t, n)

    if ds[t] == float('inf'):
        print(-1)
        print(-1)
        return

    print(ds[t])

    nexthops = set()
    for v, w in g[s]:
        if w + dt[v] == ds[t]:
            nexthops.add(v)

    if not nexthops:
        print(-1)
    else:
        print(' '.join(map(str, sorted(nexthops))))

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', line => lines.push(line.trim()));
rl.on('close', () => {
    let idx = 0;
    const [n, m] = lines[idx++].split(' ').map(Number);
    const g = Array.from({length: n + 1}, () => []);
    for (let i = 0; i < m; i++) {
        const [u, v, w] = lines[idx++].split(' ').map(Number);
        g[u].push([v, w]);
        g[v].push([u, w]);
    }
    const [s, t] = lines[idx++].split(' ').map(Number);

    if (s === t) {
        console.log(0);
        console.log(-1);
        return;
    }

    const INF = Number.MAX_SAFE_INTEGER;

    function dijkstra(src) {
        const dist = new Array(n + 1).fill(INF);
        dist[src] = 0;
        const pq = [[0, src]];
        while (pq.length > 0) {
            let minIdx = 0;
            for (let i = 1; i < pq.length; i++) {
                if (pq[i][0] < pq[minIdx][0]) minIdx = i;
            }
            const [d, u] = pq[minIdx];
            pq[minIdx] = pq[pq.length - 1];
            pq.pop();
            if (d > dist[u]) continue;
            for (const [v, w] of g[u]) {
                const nd = d + w;
                if (nd < dist[v]) {
                    dist[v] = nd;
                    pq.push([nd, v]);
                }
            }
        }
        return dist;
    }

    const ds = dijkstra(s);
    const dt = dijkstra(t);

    if (ds[t] >= INF) {
        console.log(-1);
        console.log(-1);
        return;
    }

    console.log(ds[t]);

    const nexthops = new Set();
    for (const [v, w] of g[s]) {
        if (w + dt[v] === ds[t]) {
            nexthops.add(v);
        }
    }

    if (nexthops.size === 0) {
        console.log(-1);
    } else {
        console.log([...nexthops].sort((a, b) => a - b).join(' '));
    }
});

复杂度分析

时间复杂度： $O((n + m) \log n)$ ，两次 Dijkstra 的开销。
空间复杂度： $O(n + m)$ ，存图和距离数组。