Dijkstra:
复杂度：O（n^2)
用途：求起点到终点的最短路径，不需要吧每个点走到
适用条件：
原理：利用邻接矩阵，用d数组记录最小值，用p标记是否用过这组数据。
步骤：一大for，两小for，第一个小for用来的出当前的d中的最小值，为了得到下标，第二个小for用来更新map最小值，得出结果，循环整张地图n次
模板：
#include<cstdio> #include<cstring> using namespace std; const int inf = 0x3f3f3f3f, MAX = 300; int min1,x,y,z,k,n,m; int map[MAX][MAX],p[MAX],d[MAX]; void dijkstra(int map[][MAX],int n) { for(int i = 1; i <= n ; i++) d[i] = inf; d[1] = 0; for(int i = 1; i <= n ; i++){ min1 = inf; for(int j = 1; j <= n ; j++){ if(!p[j] && d[j] < min1){ min1 = d[j]; k = j; } } p[k] = 1; for(int j = 1; j <= n ; j++){ if(!p[j] && d[j] > d[k] + map[k][j]) d[j] = d[k] + map[k][j]; } } printf("%d",d[n]); } int main(){ memset(p,0,sizeof(p)); scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) for(int j = 1; j <= n ; j++) map[i][j] = inf; for(int i = 1; i <= m ; i++){ scanf("%d%d%d",&x,&y,&z); map[x][y] =z; } dijkstra(map,n); return 0; }
原文：http://www.cnblogs.com/zero-begin/p/4354466.html