题解 | #无人机物流网络最优路径规划#

题目链接

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

题目描述

在一个由 $N$ 个配送站和 $M$ 条双向空中走廊构成的无人机物流网络中，每条走廊都有固定的能耗。给定一个配送任务的起始站 $S$ 和目的站 $T$ ，你需要计算：

从 $S$ 到 $T$ 的最低总能耗。
从 $S$ 出发的所有最短路径上的第一站（称为“下一跳”）的集合。

输出要求：

第一行输出最低能耗。
第二行按升序输出所有可能的下一跳站点。
特殊情况：若 $S=T$ ，输出 0 和 -1；若 $T$ 不可达，输出 -1 和 -1。

解题思路

这是一个在加权无向图中求解最短路径及其路径信息的典型问题。

第一部分：求解最低总能耗
- 这是一个标准的单源最短路径问题。由于所有边的权重（能耗）都是正数，最适合的算法是 Dijkstra 算法。
- 我们可以从起始站 $S$ 开始执行一次 Dijkstra 算法，计算出 $S$ 到图中所有其他站点的最短距离。最终得到的 dist[T] 就是所需的最低总能耗。
第二部分：求解所有可能的下一跳
- 寻找下一跳的关键在于，一个与 $S$ 直接相连的站点 $V$ 是一个合法的下一跳，当且仅当它位于某条从 $S$ 到 $T$ 的最短路径上。
- 这个条件可以用一个等式来判断： 最短距离(S, T) == 边(S, V)的能耗 + 最短距离(V, T)
- 为了高效地验证这个等式，我们需要知道 $S$ 到 $T$ 的最短距离，以及所有 $S$ 的邻居 $V$ 到 $T$ 的最短距离。
- 一个简单直接的方案是执行两次 Dijkstra 算法：
  - 第一次 Dijkstra: 从起点 $S$ 开始，计算出 $S$ 到所有点的最短距离，存入 dist_from_s 数组。dist_from_s[T] 就是第一问的答案。
  - 第二次 Dijkstra: 从终点 $T$ 开始，计算出 $T$ 到所有点的最短距离，存入 dist_from_t 数组。由于图是无向的，dist_from_t[V] 就等于 最短距离(V, T)。
- 整合结果：两次 Dijkstra 运行完毕后，我们遍历所有与 $S$ 直接相连的邻居站点 $V$ 。对于每个 $V$ ，我们检查等式 dist_from_s[T] == 能耗(S, V) + dist_from_t[V] 是否成立。如果成立，就将 $V$ 加入下一跳的集合。
算法步骤总结：
- 处理特殊情况：如果 $S=T$ ，直接输出 0 和 -1 并结束。
- 构建图的邻接表表示。
- 以 $S$ 为源点运行 Dijkstra，得到 dist_from_s 数组。
- 检查 dist_from_s[T] 是否可达。如果不可达，输出 -1 和 -1 并结束。
- 以 $T$ 为源点运行 Dijkstra，得到 dist_from_t 数组。
- 遍历 $S$ 的所有邻居 $V$ ，找到所有满足条件的下一跳并存入列表。
- 对下一跳列表进行升序排序。
- 输出最低总能耗和排序后的下一跳列表。

代码

cpp
java
python

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

// Dijkstra 算法
vector<long long> dijkstra(int start, int n, const vector<vector<pair<int, int>>>& adj) {
    vector<long long> dist(n + 1, INF);
    dist[start] = 0;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        long long d = pq.top().first;
        int u = pq.top().second;
        pq.pop();

        if (d > dist[u]) {
            continue;
        }

        for (const auto& edge : adj[u]) {
            int v = edge.first;
            int weight = edge.second;
            if (dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v});
            }
        }
    }
    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<int, int>>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    int s, t;
    cin >> s >> t;

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

    vector<long long> dist_from_s = dijkstra(s, n, adj);
    
    if (dist_from_s[t] == INF) {
        cout << -1 << "\n";
        cout << -1 << "\n";
        return 0;
    }

    cout << dist_from_s[t] << "\n";

    vector<long long> dist_from_t = dijkstra(t, n, adj);
    vector<int> next_hops;

    for (const auto& edge : adj[s]) {
        int v = edge.first;
        int weight = edge.second;
        if (dist_from_s[t] == weight + dist_from_t[v]) {
            next_hops.push_back(v);
        }
    }

    sort(next_hops.begin(), next_hops.end());
    for (int i = 0; i < next_hops.size(); ++i) {
        cout << next_hops[i] << (i == next_hops.size() - 1 ? "" : " ");
    }
    cout << "\n";

    return 0;
}

import java.util.*;

class Node implements Comparable<Node> {
    int id;
    long distance;

    public Node(int id, long distance) {
        this.id = id;
        this.distance = distance;
    }

    @Override
    public int compareTo(Node other) {
        return Long.compare(this.distance, other.distance);
    }
}

public class Main {
    private static final long INF = Long.MAX_VALUE;

    public static long[] dijkstra(int start, int n, List<List<Node>> adj) {
        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));

        while (!pq.isEmpty()) {
            Node current = pq.poll();
            int u = current.id;
            long d = current.distance;

            if (d > dist[u]) {
                continue;
            }

            for (Node neighbor : adj.get(u)) {
                int v = neighbor.id;
                long weight = neighbor.distance;
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        return dist;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        List<List<Node>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();
            adj.get(u).add(new Node(v, w));
            adj.get(v).add(new Node(u, w));
        }

        int s = sc.nextInt();
        int t = sc.nextInt();

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

        long[] distFromS = dijkstra(s, n, adj);

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

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

        long[] distFromT = dijkstra(t, n, adj);
        List<Integer> nextHops = new ArrayList<>();

        for (Node neighbor : adj.get(s)) {
            int v = neighbor.id;
            long weight = neighbor.distance;
            if (distFromS[t] == weight + distFromT[v]) {
                nextHops.add(v);
            }
        }

        Collections.sort(nextHops);
        for (int i = 0; i < nextHops.size(); i++) {
            System.out.print(nextHops.get(i) + (i == nextHops.size() - 1 ? "" : " "));
        }
        System.out.println();
    }
}

import heapq

INF = float('inf')

def dijkstra(start, n, adj):
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]

    while pq:
        d, u = heapq.heappop(pq)

        if d > dist[u]:
            continue

        for v, weight in adj[u]:
            if dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                heapq.heappush(pq, (dist[v], v))
    return dist

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

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

    dist_from_s = dijkstra(s, n, adj)

    if dist_from_s[t] == INF:
        print(-1)
        print(-1)
        return

    print(dist_from_s[t])

    dist_from_t = dijkstra(t, n, adj)
    next_hops = []

    for v, weight in adj[s]:
        if dist_from_s[t] == weight + dist_from_t[v]:
            next_hops.append(v)
            
    next_hops.sort()
    print(*next_hops)

if __name__ == "__main__":
    main()

算法及复杂度

算法：Dijkstra 算法
时间复杂度： $\mathcal{O}(M \log N)$ ，其中 $N$ 是配送站的总数， $M$ 是空中走廊的数量。算法的主体是运行两次 Dijkstra 算法，使用优先队列实现的 Dijkstra 算法时间复杂度为 $\mathcal{O}(M \log N)$ 。
空间复杂度： $\mathcal{O}(N + M)$ ，用于存储图的邻接表、距离数组以及优先队列。