D2 狄克斯特拉算法 • EH's Blog

题目情境#

题目链接：

https://www.luogu.com.cn/problem/P3371 ↗

https://www.luogu.com.cn/problem/P4779 ↗

题目描述

如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入格式

第一行包含三个整数 $n,m,s$ ，分别表示点的个数、有向边的个数、出发点的编号。

接下来 $m$ 行每行包含三个整数 $u,v,w$ ，表示一条 $u \to v$ 的，长度为 $w$ 的边。

输出格式

输出一行 $n$ 个整数，第 $i$ 个表示 $s$ 到第 $i$ 个点的最短路径，若不能到达则输出 $2^{31}-1$ 。

输入 #1

plaintext

输出 #1

0 2 4 3

plaintext

对于 $100\%$ 的数据： $1 \le n \le 10^4$ ， $1\le m \le 5\times 10^5$ ， $1\le u,v\le n$ ， $w\ge 0$ ， $\sum w< 2^{31}$ ，保证数据随机。

堆优化版题目：

题目描述

给定一个 $n$ 个点， $m$ 条有向边的带非负权图，请你计算从 $s$ 出发，到每个点的距离。

数据保证你能从 $s$ 出发到任意点。

输入格式

第一行为三个正整数 $n, m, s$ 。第二行起 $m$ 行，每行三个非负整数 $u_i, v_i, w_i$ ，表示从 $u_i$ 到 $v_i$ 有一条权值为 $w_i$ 的有向边。

输出格式

输出一行 $n$ 个空格分隔的非负整数，表示 $s$ 到每个点的距离。

输入 #1

plaintext

输出 #1

0 2 4 3

plaintext

$1 \leq n \leq 10^5$ ；

$1 \leq m \leq 2\times 10^5$ ；

$s = 1$ ；

$1 \leq u_i, v_i\leq n$ ；

$0 \leq w_i \leq 10 ^ 9$ ,

$0 \leq \sum w_i \leq 10 ^ 9$ 。

算法解析：#

堆优化版：

Python代码实现#

class Edge():
    def __init__(self, v, w):
        self.v = v
        self.w = w

def dijkstra(s):
    for i in range(n + 1):
        d[i] = int(2 ** 31 - 1)
    d[s] = 0
    for i in range(1, n):
        u = 0
        for j in range(1, n + 1):
            if not vis[j] and d[j] < d[u]:
                u = j
        vis[u] = 1
        for ed in e[u]:
            v = ed.v
            w = ed.w
            if d[v] > d[u] + w:
                d[v] = d[u] + w

n, m, s = map(int, input().split())
e = [[] for i in range(n + 1)]
d = [0] * (n + 1)
vis = [0] * (n + 1)
for i in range(m):
    a, b, c = map(int, input().split())
    e[a].append(Edge(b, c))

dijkstra(s)
for i in range(1, n + 1):
    print(d[i], end=" ")

python

import heapq

class Edge():
    def __init__(self, v, w):
        self.v = v
        self.w = w

def dijkstra(s):
    for i in range(n + 1):
        d[i] = int(1e20)
    d[s] = 0
    q = []
    heapq.heappush(q, [0, s])
    while len(q) > 0:
        t = heapq.heappop(q)
        u = t[1]
        if vis[u]:
            continue
        vis[u] = 1
        for ed in e[u]:
            v = ed.v
            w = ed.w
            if d[v] > d[u] + w:
                d[v] = d[u] + w
                heapq.heappush(q, [d[v], v])

n, m, s = map(int, input().split())
e = [[] for i in range(n + 1)]
d = [0] * (n + 1)
vis = [0] * (n + 1)
for i in range(m):
    a, b, c = map(int, input().split())
    e[a].append(Edge(b, c))

dijkstra(s)
for i in range(1, n + 1):
    print(d[i], end=" ")

python

C++代码实现#

//Dijkstra
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define inf 2147483647
using namespace std;

int n,m,s,a,b,c;
const int N=100010;
struct edge{int v,w;};
vector<edge> e[N];
int d[N], vis[N];

void dijkstra(int s){
  for(int i=0;i<=n;i++)d[i]=inf;
  d[s]=0;
  for(int i=1;i<n;i++){//枚举次数
    int u=0;
    for(int j=1;j<=n;j++)//枚举点
      if(!vis[j]&&d[j]<d[u]) u=j;
    vis[u]=1; //标记u已出圈
    for(auto ed:e[u]){//枚举邻边
      int v=ed.v, w=ed.w;
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
      }
    }
  }
}
int main(){
  cin>>n>>m>>s;
  for(int i=0; i<m; i++){
    cin>>a>>b>>c;
    e[a].push_back({b,c});
  }
  dijkstra(s);
  for(int i=1;i<=n;i++)
    printf("%d ",d[i]);
  return 0;
}

//堆优化Dijkstra
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

const int N=100010;
int n,m,s,a,b,c;
struct edge{int v,w;};
vector<edge> e[N];
int d[N],vis[N];

void dijkstra(int s){
  memset(d,0x3f,sizeof d); d[s]=0;
  priority_queue<pair<int,int>> q;
  q.push({0,s});
  while(q.size()){
    auto t=q.top(); q.pop();
    int u=t.second;
    if(vis[u])continue; //再出队跳过
    vis[u]=1; //标记u已出队
    for(auto ed : e[u]){
      int v=ed.v, w=ed.w;
      if(d[v]>d[u]+w){
        d[v]=d[u]+w;
        q.push({-d[v],v}); //大根堆
      }
    }
  }
}
int main(){
  cin>>n>>m>>s;
  for(int i=0; i<m; i++)
    cin>>a>>b>>c, e[a].push_back({b,c});
  dijkstra(s);
  for(int i=1;i<=n;i++) printf("%d ",d[i]);
}