这个算法适用于求单源最短路径，从一点出发，到其余个点的最短路径。
算法要点：
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[];
int book[];
int maps[][];
const int MAX = ;//定义一个最大值，距离不会超过这个 int main()
{
int i,j,q;//循环变量
int n,m;
int x,y,z;
int index,indexNumber;//离当前点最近的点的坐标和坐标
cin>>n>>m;//输入N*N的图，和M条边对应的值 for (i = ; i <= n; i++)//初始化dis距离
dis[i] = MAX; for (i = ; i <= n; i++)//初始化maps里面的所有距离
for (j = ; j <= n; j++)
if(i != j)
maps[i][j] = MAX;
else
maps[i][j] = ; for (i = ; i <= m; i++)
{
cin>>x>>y>>z;//输入x到y的距离为z
maps[x][y] = z;
if(x==)
dis[y] = z;//如果是x=1，那么就是1点到别的点的距离，用dis保存
} dis[] = ;//自己到自己肯定是0
book[] = ;//默认从1点开始找
for (q = ; q <= n; q++)
{
index=;
indexNumber = MAX;
for (j = ; j <= n; j++)
{
if(book[j] == )
{
if(dis[j] < indexNumber)
{
indexNumber = dis[j];
index = j;
}
}
} book[index] = ;//证明这个点已经来过
for (i = ; i <= n; i++)//循环N次
{
if(book[i] == && maps[index][i] != MAX)//松弛过的点和不可能通过松弛的点先扔掉
{
if(dis[i] > dis[index] + maps[index][i])//从1点到这个点如果比中间加上index点还要长，就松弛
{
dis[i] = dis[index] + maps[index][i];
}
} }
} for (i = ; 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数组去标识这个点是不是已经是一个确定的值，已经是最短的了，但是这样的话就不能处理负数距离的情况，所以还是有一定的使用范围的，使用时需要注意。