题解 | #【模板】单源最短路Ⅲ ‖ 非负权图#

题目链接

【模板】单源最短路Ⅲ ‖ 非负权图

题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的有向赋权图，边权均为非负整数。指定一个起点 $S$ ，你需要计算从起点 $S$ 到图中所有顶点的最短路径长度。

如果一个顶点无法从起点到达，则其最短路径长度为 $-1$ 。
起点到其自身的最短路径长度为 $0$ 。

解题思路

本题是典型的单源最短路径问题，且所有边权均为非负，因此最适合使用 Dijkstra 算法 求解。由于图的规模可能较大，需要使用**堆（优先队列）**来进行优化，以达到题目要求的时间复杂度。

Dijkstra 算法（堆优化）

Dijkstra 算法是一种贪心算法，用于寻找图中从单一源点到所有其他顶点的最短路径。其核心思想是：

维护一个距离数组 dist，其中 dist[i] 存儲从起点 $S$ 到顶点 $i$ 的当前已知最短路径长度。
初始化 dist 数组，将起点的距离 dist[S] 设为 $0$ ，其他所有顶点的距离设为无穷大。
使用一个优先队列（最小堆）来存储待处理的顶点，优先队列中元素的优先级由其 dist 值决定（dist 值越小，优先级越高）。初始时，将起点 (0, S) 放入队列。
当优先队列不为空时，重复以下步骤：

a. 从队列中取出距离最小的顶点 $u$ （及其距离 $d$ ）。

b. 如果顶点 $u$ 已经被访问过（即已经找到了其最短路径），则跳过。

c. 标记顶点 $u$ 为已访问。

d. 遍历所有从 $u$ 出发的边 $(u, v)$ ，其权重为 $w$ 。对于每个邻接顶点 $v$ ，尝试进行松弛操作：
- 如果 dist[u] + w < dist[v]，说明经由 $u$ 到达 $v$ 的路径比当前已知的到 $v$ 的路径更短。
- 更新 dist[v] = dist[u] + w。
- 将新的路径信息 (dist[v], v) 加入优先队列。
算法结束后，dist 数组中就保存了从起点 $S$ 到所有顶点的最短路径长度。若某个顶点的 dist 值仍为无穷大，则表示该顶点不可达。

数据结构

邻接表：用于存储图的结构。vector<pair<int, int>> adj[N]，其中 adj[u] 存储所有从 $u$ 出发的边，每条边表示为 {v, w}，即终点和权重。
优先队列：用于高效地获取当前 dist 值最小的未访问顶点。在 C++ 中，priority_queue 默认是最大堆，我们可以通过存储 { -distance, vertex } 来模拟最小堆。

代码

c++
java
python

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

using namespace std;

const long long INF = 1e18;

struct Edge {
    int to;
    int weight;
};

struct Node {
    int id;
    long long dist;

    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

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

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

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

    vector<long long> dist(n + 1, INF);
    dist[s] = 0;

    priority_queue<Node, vector<Node>, greater<Node>> pq;
    pq.push({s, 0});

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        int u = current.id;
        long long d = current.dist;

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

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

    for (int i = 1; i <= n; ++i) {
        if (dist[i] == INF) {
            cout << -1 << (i == n ? "" : " ");
        } else {
            cout << dist[i] << (i == n ? "" : " ");
        }
    }
    cout << "\n";

    return 0;
}

import java.util.*;

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

    static class Edge {
        int to;
        int weight;

        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    static class Node implements Comparable<Node> {
        int id;
        long dist;

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

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

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

        List<List<Edge>> 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 Edge(v, w));
        }

        long[] dist = new long[n + 1];
        Arrays.fill(dist, INF);
        dist[s] = 0;

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

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

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

            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                int w = edge.weight;
                if (dist[u] != INF && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }

        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) {
                System.out.print(-1 + (i == n ? "" : " "));
            } else {
                System.out.print(dist[i] + (i == n ? "" : " "));
            }
        }
        System.out.println();
    }
}

import heapq

def dijkstra(n, adj, start_node):
    dist = {i: float('inf') for i in range(1, n + 1)}
    dist[start_node] = 0
    
    pq = [(0, start_node)]
    
    while pq:
        d, u = heapq.heappop(pq)
        
        if d > dist[u]:
            continue
            
        for v, w in adj.get(u, []):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
                
    return dist

def main():
    n, m, s = map(int, input().split())
    
    adj = {}
    for _ in range(m):
        u, v, w = map(int, input().split())
        if u not in adj:
            adj[u] = []
        adj[u].append((v, w))
        
    distances = dijkstra(n, adj, s)
    
    result = []
    for i in range(1, n + 1):
        if distances[i] == float('inf'):
            result.append(-1)
        else:
            result.append(distances[i])
    
    print(*result)

if __name__ == "__main__":
    main()