这个算法适用于求单源最短路径，从一点出发，到其余个点的最短路径。
算法要点：
1、用二维数组存放点到点的距离-----不能相互到达的点用MAX代替距离
2、用dis数组存放源点到任意其他一点的距离----dis【5】表示源点到5点的距离为dis【5】中的值
3、用book数组记录已经确定最小dis的点
4、用index和indexNumber存放估计值的点
5、从源点到这个点如果比中间加上估计值的点还要长，就松弛
算法模型：
for(循环N次)
｛
for(循环找到估计值点)
｛
估计值点是现在的dis中距离源点最近的点。
｝
book数组记录已经走过这个估计值点
for(循环N次)
｛
if（dis【循环值】> dis【估计值】+maps【估计值】【循环值】）//从源点到这个点如果比中间加上估计值的点还要长，就松弛
dis【循环值】= dis【估计值】+maps【估计值】【循环值】
｝
｝
#include<cstdio> #include<cstdlib> #include<iostream> using namespace std; /*Dijkstra*/ int dis[100]; int book[100]; int maps[100][100]; const int MAX = 99999;//定义一个最大值，距离不会超过这个 int main() { int i,j,q;//循环变量 int n,m; int x,y,z; int index,indexNumber;//离当前点最近的点的坐标和坐标 cin>>n>>m;//输入N*N的图，和M条边对应的值 for (i = 1; i <= n; i++)//初始化dis距离 dis[i] = MAX; for (i = 1; i <= n; i++)//初始化maps里面的所有距离 for (j = 1; j <= n; j++) if(i != j) maps[i][j] = MAX; else maps[i][j] = 0; for (i = 1; i <= m; i++) { cin>>x>>y>>z;//输入x到y的距离为z maps[x][y] = z; if(x==1) dis[y] = z;//如果是x=1，那么就是1点到别的点的距离，用dis保存 } dis[1] = 0;//自己到自己肯定是0 book[1] = 1;//默认从1点开始找 for (q = 1; q <= n; q++) { index=0; indexNumber = MAX; for (j = 1; j <= n; j++) { if(book[j] == 0) { if(dis[j] < indexNumber) { indexNumber = dis[j]; index = j; } } } book[index] = 1;//证明这个点已经来过 for (i = 1; i <= n; i++)//循环N次 { if(book[i] == 0 && maps[index][i] != MAX)//松弛过的点和不可能通过松弛的点先扔掉 { if(dis[i] > dis[index] + maps[index][i])//从1点到这个点如果比中间加上index点还要长，就松弛 { dis[i] = dis[index] + maps[index][i]; } } } } for (i = 1; i <= n; i++) { cout<<dis[i]<<" "; } cout<<endl; } /* 测试数据 6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4 R:0 1 8 4 13 17 */
这个算法还能根据实际情况去优化，时间复杂度还能减少，优化下次再继续研究。
需要注意的是，这个算法利用贪心的思想，尽可能找到最短中的最短，已经最短的了，就已经是最短的了，就不变了，也就是为什么会有book数组去标识这个点是不是已经是一个确定的值，已经是最短的了，但是这样的话就不能处理负数距离的情况，所以还是有一定的使用范围的，使用时需要注意。