迪杰斯特拉算法是最典型的 单源最短路径算法,用于计算一个节点到其余所有节点的最短路径。(缺点:该算法中不存在负权边)
#include<iostream> #include<cstdio> #include<cstring> using namespace std; #define MAX 115 #define INF 0x3f3f3f3 int mp[MAX][MAX] , dis[MAX]; //dis用于保存起点到各个点的距离 bool vis[MAX]; //用于点的判重 void Dijkstra(int n) { int minx,flag = 1; for(int i = 1;i <= n;i++) { dis[i] = mp[1][i]; //记录刚开始起点到各个点的距离 vis[i] = true; //刚开始所有的点都是新点 } vis[1] = false; for(int i = 1;i <= n;i++) { minx = INF; for(int j = 1;j <= n;j++) { if(vis[j] && dis[j] < minx) //选取起点到各个点中最短的那条边而且这个点是新点 { minx = dis[j]; flag = j; //记录位置 } } vis[flag] = false; //将这个点标记为旧点,因为已经找到从起点到该点的最短路径了 if(minx == INF) break;//如果所有的点都为旧点,那么最短路径算法也就完成了 for(int j = 1;j <= n;j++) { if(vis[j] && (dis[flag] + mp[flag][j] < dis[j])) dis[j] = dis[flag] + mp[flag][j]; } } } int main() { int n,m,a,b,c; while(~scanf("%d%d",&n,&m)) { if(n == 0 && m == 0) break; for (int i=1;i<=MAX;i++) for (int j=1;j<=MAX;j++) mp[i][j]=INF; ///重新设为最大值 for(int i = 1;i <= m;i++) { scanf("%d%d%d",&a,&b,&c); mp[a][b] = mp[b][a] = c;//代表点a到点b的距离为c } Dijkstra(n); cout << dis[n] << endl; } return 0; }