最短路径：迪杰斯特拉算法

首先推荐两个博客，帮我终于弄清楚了迪杰斯特拉算法
思路写得很好：https://blog.****.net/qq_39521554/article/details/79333690
这里的这个代码实现很不错，简单易懂：https://blog.51cto.com/ahalei/1387799

需要注意的是，迪杰斯特拉算法不能对权值有负数的图进行处理。dis数组是存放的源点到每个点最短路径的估计值，book数组是标记这个点的最短路径是否算出。

参考代码：

#include<iostream>
using namespace std;

const int inf = 0x3f3f3f3f;

int main()
{
	int n, m, min, minindex;			//n为顶点个数，m为边的条数 
	int e[10][10], dis[10], book[10];		//存储图
	cin >> n >> m;
	//初始化
	for(int i = 1;i <= n;i++)
	{
		for(int j = 1;j <= n;j++)
		{
			if(i == j)		//自己到自己，权值为0 
				e[i][j] = 0;	
			else 			//否则初始化为无穷大 
				e[i][j] = inf;
		}
	} 
	//读入边
	for(int i = 1;i <= m;i++)
	{
		int t1, t2, t3;
		cin >> t1 >> t2 >> t3;
		e[t1][t2] = t3;			 
		//e[t2][t1] = t3;		有向图 
	}
	//初始化dis数组，1号顶点到其余各顶点的初始长度（如果求其他顶点做源点，这里就换一下） 
	for(int i = 1;i <= n;i++)
		dis[i] = e[1][i];
	//初始化book数组，用于标记一个点的最短路径是否算出 
	for(int i = 1;i <= n;i++)
		book[i] = 0;
	book[1] = 1;
	
	//Dijkstra算法核心语句
	for(int i = 1;i <= n - 1;i++)		//做n - 1次迭代，循环完毕后，代表所有节点的最短路径都出来了，算法结束 
	{
		min = inf;						//记录dis值最小的那个
		minindex = 0; 					//最小节点的序号 
		for(int i = 2;i <= n;i++)
		{
			if(dis[i] < min && book[i] != 1)	//不能是dis值已经确定的节点 
			{
				min = dis[i];	
				minindex = i;			//记录下dis最小的节点 
			}
		}
		book[minindex] = 1;
		//对minindex节点进行出边
		for(int j = 1;j <= n;j++)
		{
			if(e[minindex][j] < inf && e[minindex][j] > 0)
			{
				if(dis[j] > e[minindex][j] + dis[minindex])
					dis[j] = e[minindex][j] + dis[minindex];
			}
		} 
		//出边结束后，再回到上面继续迭代，找下一个minindex即可 
	}
	
	//输出结果
	for(int i = 2;i <= n;i++)
	{
		cout << "1号顶点到 " << i << "号顶点的最短路径为：";
		cout << dis[i] << endl;
	} 
	return 0;
}

测试数据：
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
运行结果：