题目描述
给定一个n个点m条边的有向图,图中可能存在重边和自环,所有边权均为正值。
请你求出1号点到n号点的最短距离,如果无法从1号点走到n号点,则输出-1。
输入格式
第一行包含整数n和m。
接下来m行每行包含三个整数x,y,z,表示存在一条从点x到点y的有向边,边长为z。
输出格式
输出一个整数,表示1号点到n号点的最短距离。
如果路径不存在,则输出-1。
数据范围
1≤n≤500,
1≤m≤105,
图中涉及边长均不超过10000。
输入样例:
3 3
1 2 2
2 3 1
1 3 4
输出样例:
3
思路
Dijkstra 的原理其实跟生活中的一些自然现象完全一样
把每1个顶点想象成是1块小石头
每1条边想象成是1条绳子,每一条绳子都连接着2块小石头,边的权值就是绳子的长度
将小石头和绳子平放在一张桌子上(下图是一张俯视图,图中黄颜色的是桌子)
接下来想象一下,手拽着小石头A,慢慢地向上提起来,远离桌面
B、D、C、E会依次离开桌面
最后绷直的绳子就是A到其他小石头的最短路径
有一个很关键的信息
后离开桌面的小石头
都是被先离开桌面的小石头拉起来的
关键代码:
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i ++){
int t = -1; //表示还没有确认
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
st[t] = true;
for(int j = 1; j <= n; j ++){
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
我们接下来看个列子
绿色
已经“离开桌面”
已经确定了最终的最短路径
红色:更新了最短路径信息
代码中t选中A,更新A的所有最短路径长度,将A的st[A] = true;
代码中t选中B,更新A->B->其他点 最短路径,将B的st[B] = true;
代码中t选中D,更新A->D->其他点 最短路径,将D的st[D] = true;
代码中t选中C,更新A->D->C->其他点 最短路径,将C的st[C] = true;
代码中t选中E,更新A->D->C->E->其他点 最短路径,将E的st[E] = true;
结束
它采用松弛操作(Relaxation):更新2个顶点之间的最短路径
这里一般是指:更新源点到另一个点的最短路径
松弛操作的意义:尝试找出更短的最短路径
总结
① dist[1] = 0, dist[i] = -INF
② for i in 1…n:
t <- 不在s中 要遍历每一个点 n次
s <- t
用t更新其他点 更改每一个点 n次
总的时间复杂度O(n^2)
java
import java.util.Scanner;
public class Main{
static int n, m;
static int N = 510;
static int[][] g = new int[N][N];
static int[] dist = new int[N];
static boolean[] st = new boolean[N];
private static int dijkstra() {
dist[1] = 0; // 第一次最小的最短路径值为1 -> 1 距离为0
for (int i = 1; i < n; i++) { //遍历n - 1次,因为第一个点的距离值默认为0,每个顶点都参与最短路径
int t = -1; // 未确定
for (int j = 1; j <= n; j++) {
if (!st[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
// 加入到以访问的顶点中
st[t] = true;
for (int j = 1; j <= n; j++) {
dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
}
}
if (dist[n] == 0x3f3f3f) {
return -1;
}
return dist[n];
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
g[i][j] = 0x3f3f3f;
}
}
for (int i = 0; i < N; i++) {
dist[i] = 0x3f3f3f;
}
while (m -- > 0) {
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
g[a][b] = Math.min(g[a][b], c);
}
int t = dijkstra();
System.out.println(t);
}
}
python
N = 510
g = [[0x3f3f3f] * N for i in range(N)]
dist = [0x3f3f3f] * N
st = [False] * N
n, m = 0, 0
def dijkstra():
dist[1] = 0
for i in range(0, n):
t = -1
for j in range(1, n + 1):
if not st[j] and (t == -1 or dist[t] > dist[j]):
t = j
st[t] = True
for j in range(1, n + 1):
dist[j] = min(dist[j], dist[t] + g[t][j])
if dist[n] == 0x3f3f3f:
return -1
return dist[n]
def main():
global n, m
n, m = map(int, input().split())
for i in range(m):
a, b, c = map(int, input().split())
g[a][b] = min(g[a][b], c)
t = dijkstra()
print(t)
if __name__ == '__main__':
main()
c ++
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 510;
int n, m;
int g[N][N];
int dist[N];
bool st[N];
int dijkstra(){
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
for(int i = 0; i < n; i ++){
int t = -1; //表示还没有确认
//找下一个最短距离的点
//比如 dist[1] = 0, 第一次为t = 1; 其他节点计算距离
//假设有1 -> 2 = 1 1 -> 3 = 2,
//显然下一次找到的最短距离的点为2,沿着1 -> 2更新其他距离点
for(int j = 1; j <= n; j ++){
if(!st[j] && (t == -1 || dist[t] > dist[j])){
t = j;
}
}
st[t] = true;
for(int j = 1; j <= n; j ++){
dist[j] = min(dist[j], dist[t] + g[t][j]);
}
}
if(dist[n] == 0x3f3f3f3f) return -1;
return dist[n];
}
int main(){
scanf("%d%d", &n, &m);
memset(g, 0x3f, sizeof g);
while(m --){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
//自环不需要考虑,自己到自己最短路径就为0,
//比如最短路径中,a -> b为4 b -> b为1,那么如果遍历资环a -> b -> b为5,显然大于a -> b 4
//多重边解决如下
g[a][b] = min(g[a][b], c);
}
int t = dijkstra();
printf("%d\n", t);
return 0;
}
大佬的类比太强了,基本上每个题解都看大佬的
哈哈,谢谢支持
太强了%%%