單源最短路徑Dijkstra
關于原理請看：看文—看圖
注意Dijkstra不能處理存在負邊權的題目
由于“估計值”5<6,所以3先確定了，3確定了之后再確定的2，所以1->3的距離不會變
本文對代碼進行解釋
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#define INF 0x3f3f3f
using namespace std;
int map[1005][1005];
int dis[1005],book[1005];
int main() {
int n,m;
while(cin>>m>>n) {
memset(dis,0,sizeof(dis));
memset(book,0,sizeof(book));
memset(map,INF,sizeof(map));
for(int i=1; i<=n; i++)
map[i][i]=0;//自己到自己為0，其他初始化為正無窮
for(int i=1; i<=m; i++) {
int x,y,z;
cin>>x>>y>>z;
map[x][y]=z;
}
for(int i=1; i<=n; i++)
dis[i]=map[1][i];//以1為源，存盤1到別的點的“估計值”
book[1]=1;//點1是確定值
for(int i=1; i<=n-1; i++) {
int min=INF;
int u=1;
for(int j=1; j<=n; j++) {
if(book[j]==0 && dis[j]<min) {
min=dis[j];
u=j;//在估計值中選取權最小的
}
}
book[u]=1;//把1到別的點的“估計值”的權最小的點變成確定值
for(int j=1; j<=n; j++) {
if(map[u][j]<INF ) {//找到與u相連的點，設為x
if(dis[j]>dis[u]+map[u][j] && book[j]==0 )//更新估計值,確定值不變
dis[j]=dis[u]+map[u][j];//1->u,u->x的線路比1->x的線路優，所以更新1->x的線路
}
}
}
cout<<dis[n]<<endl;//dis[n]即1->x的最短路
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/280692.html
標籤：其他
上一篇：雙非碩士的辛酸求職之旅--談談我是如何同時找到Java、Python、Go等開發崗和國企銀行的科技崗位Offer
下一篇：C++7.3銷售系統練習