Dijkstra（单源最短路径）

         <!--一个博主专栏付费入口结束-->
        <link rel="stylesheet" href="https://csdnimg.cn/release/phoenix/template/css/ck_htmledit_views-d284373521.css">
                                    <link rel="stylesheet" href="https://csdnimg.cn/release/phoenix/template/css/ck_htmledit_views-d284373521.css">
            <div class="htmledit_views" id="content_views">
                                        <p><strong>&nbsp;Dijkstra的主要特点是以起始点为中心向外层层拓展（广度优先搜索思想），直到拓展到终点为止。</strong></p>

用二维数组edge表示顶点之间的关系，dis数组表示源点到其余各点的距离，book数组表示dis对应的距离是否是最短距离。

dis数组初始化为【0，2，6，4】，book为【1，0，0，0】

• 既然是求点1到其余各点的距离，那么，就找一个离点1最近的点。通过dis数组可知，为点2，这个图所有的边为正数，如果通过另一个点周转，必然大于点1到点2的距离。因此，book更新为【1，1，0，0】。然后，更新dis数组，查看是否有点经过点2周转之后，到达源点1的距离缩短了。发现dis[3] = 6, dis[2] + edge[2][3] = 5 < 6，dis更新为【0，2，5，4】（这个更新的过程叫“松弛”）
• 重复上述的过程，第二轮迭代找到的点为点4，更新book为【1，1，0，1】，剩下的点3经过点4周转并不能缩小到源点的距离，因此，dis依然为【0，2，5，4】；
• 第三轮迭代，确定点3，book更新为【1，1，1，1】，算法结束。

可以发现，每一轮迭代都可以确定一个点到源点的距离，因此，最多进行n-1次“松弛”，就可以结束算法。

算法图解，参考该博客：https://blog.csdn.net/heroacool/article/details/51014824

代码

#include <iostream>




using namespace std;




const int inf = 0x3f3f3f3f;




int edge[5][5] = 



{



	{-1,-1,-1,-1,-1},



	{-1, 0, 2, 6, 4},



	{-1, inf, 0,3, inf},



	{-1, 7, inf, 0, 1},



	{-1, 5, inf, 12, 0}



};








int main() {



	const int n = 4;//点的数量




	int dis[n+1];//当前各点到源点的距离




	int book[n+1];//各点到源点是否为最小值








	//初始化，设源点为n1




	for (int i = 1; i <= n; ++i)



		dis[i] = edge[1][i];







	//book数组初始化




	memset(book, 0, sizeof(book));



	book[1] = 1;







	int min;//当前，未确定最短路径的点，到源点的最小距离大小




	//Dijkstra算法核心语句




	for (int i = 1; i <= n - 1; ++i) {



		//找到离1号顶点最近的顶点




		min = inf;



		int u;



		for (int j = 1; j <= n; ++j) {



			if (book[j] == 0 && dis[j] < min) {



				min = dis[j];



				u = j;



			}



		}



		//每轮迭代都可以确定一个点到源点的最短距离，因此只要迭代n-1轮




		book[u] = 1;



		//通过已经确定的点，对dis数组进行更新




		//（未确定的点通过点u，缩小了到源点的距离）




		for (int v = 1; v <= n; ++v) {



			if (edge[u][v] < inf) {



				if (dis[v] > dis[u] + edge[u][v])



					dis[v] = dis[u] + edge[u][v];



			}



		}



	}



	//输出结果




	for (int i = 1; i <= n; ++i)



		cout << dis[i] << ' ';



	system("pause");



	return 0;



}