http://acm.hdu.edu.cn/showproblem.php?pid=2544
迪杰斯特拉算法
#include<stdio.h> #include <string.h> #define INF 0x3f3f3f int n, m; int map[110][110]; void init() //初始化图,权值无穷大 { int i,j; for (i=1; i<=n; i++) { for (j=1; j<=n; j++) map[i][j] = INF; map[i][i] = 0; } } void input() { int i; int a,b,c; for (i=0; i<m; i++) { scanf("%d%d%d",&a,&b,&c); if (map[a][b]>c) map[a][b] = map[b][a] = c; //无向图 } } void dijkstra() { int i,j,mindis,key; int dis[110]; //存放最短路长度(会被更新,不过最后的一定是最短路) int used[110]; //标志数组,这个点有最短路了就标记1 for (i=1; i<=n; i++) //初始化每个点的最短路为INF { dis[i] = INF; used[i] = 0; //全部点都没找过 } dis[1] = 0; while (1) { mindis = INF; key = -1; for (i=1; i<=n; i++) //找权(路径)最短的点 { if (!used[i]&&dis[i]<mindis) { mindis = dis[i]; key = i; //找到了赋值给key } } if (key==-1||key==n) //没有路径最短的点了或者找到最后一个点了就结束了 break; used[key] = 1; //找到了就标记为1 for (j=1; j<=n; j++) //从key点出发找最短路(权)的点 { if (!used[j]&&dis[j]>dis[key] + map[key][j]) dis[j] = dis[key] + map[key][j]; //修改最短路长度 } } printf("%d\n",dis[n]); } int main() { while (scanf("%d%d",&n,&m)! =EOF&&n&&m) { init(); input(); dijkstra(); } return 0; }