dijkstra算法求最短路的两个基础,使用的点到原点的距离越来越大,不能含有负权边。这样可以保证子结构路径最短时总路径一定最短。当包含负权边时,最优子结构的性质就会消失,因为每个点只能更新一次。
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=510;
int g[N][N],dist[N];
bool st[N];
int n,m;
int dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
//n次遍历
for(int i=0;i<n;i++){
int t=-1;
//遍历所有节点
for(int j=1;j<=n;j++){
//找到未被访问且距离0点最近的点,t=-1为了解决只剩下一个节点未确定的情况
if(!st[j]&&(t==-1||dist[j]<dist[t]))
t=j;
}
st[t]=true;
//用选定的最小距离节点更新其他节点
for(int j=1;j<=n;j++){
if(dist[j]>dist[t]+g[t][j])
dist[j]=dist[t]+g[t][j];
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
int main(){
cin>>n>>m;
//首先将全部权重设置为无限大表示不可达
memset(g,0x3f,sizeof g);
//数据读入 算法保证不选选自环为最短路
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=min(g[a][b],c);
}
int t=dijkstra();
cout<<t<<endl;
return 0;
}