【Dijkstra算法】求图的最短路

本文主要是介绍【Dijkstra算法】求图的最短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式
第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式
输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

问题求解

集合S为已经确定最短路径的点集。

1. 初始化距离
   一号结点的距离为零，其他结点的距离设为无穷大（看具体的题）。
2. 循环n次，每一次将集合S之外距离最短X的点加入到S中去（这里的距离最短指的是距离1号点最近。：
   即 在状态未被更新的点里找距离最短的点
   从该点出发，更新其邻接点的距离
   点X的路径一定最短，基于贪心，严格证明待看）。然后用点X更新X邻接点的距离。

# include <iostream>
# include <cstring>using namespace std;
const int N = 100010;int e[N], ne[N], h[N],wb[N];
int dist[600];
bool state[600];
int n,m,idx;void add(int a, int b ,int w){e[idx] = b;wb[idx] = w;ne[idx] = h[a];h[a] = idx++;}void dijkstra(){dist[1] = 0;for(int i =1; i<=n; i++){int t = -1;int j;for(j=1; j<=n; j++){if(!state[j] && (t==-1|| dist[j]<dist[t])){t = j;}}state[t] = 1;for(int u = h[t]; u !=-1 ; u =ne[u]){int c = e[u];if(wb[u] + dist[t] < dist[c]){dist[c] = wb[u] + dist[t];}}}
}int main(){memset(h ,-1, sizeof(h));memset(dist, 0x3f, sizeof(dist));cin>>n>>m;int a,b,w;for(int i =0; i<m; i++){cin>>a>>b>>w;add(a,b,w);}dijkstra();if(dist[n]!=0x3f3f3f3f){cout<<dist[n]<<endl;}else{cout<<-1;}}

这篇关于【Dijkstra算法】求图的最短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---