【算法】图的应用之Dijkstra算法--单源最短路径的求解

缺乏、安全感 2022-06-13 07:58 187阅读 0赞

求一个图中的顶点到其他顶点的最短路径，如下图：

![Center][]

例如求解顶点1到各个顶点的最短路径，由图可知：

顶点1到1的最短路径为0

顶点1到2的最短路径为1

顶点1到3的最短路径为8

顶点1到4的最短路径为4

顶点1到5的最短路径为13

顶点1到6的最短路径为17

算法的基本思想：每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展

最终得到源点到其余所有点的最短的路径。

代码实现：

#define _CRT_SECURE_NO_DEPRECATE
    #include<stdio.h>
    #include<stdlib.h>
    
    int main()
    {
    
    	int e[10][10], dis[10], book[10], i, j, n, m, t1, t2, t3, u, v, min;
    	int inf = 99999999;
    	printf("请输入顶点n和边数m->\n");
    	scanf("%d %d", &n, &m);
    	//初始化
    	for (i = 1; i <= n; i++)
    	{
    		for (j = 1; j <= n; j++)
    		{
    			if (i == j)
    			{
    				e[i][j] = 0;
    			}
    			else
    			{
    				e[i][j] = inf;
    			}
    		}
    	}
    	printf("请输入顶点t1,t2以及两个顶点之间的权值t3->\n");
    	//读入边
    	for (i = 1; i <= m; i++)
    	{
    		scanf("%d %d %d", &t1, &t2, &t3);
    		e[t1][t2] = t3;
    	}
    
    	for (i = 1; i <= n; i++)
    	{
    		dis[i] = e[1][i];
    	}
    	for (i = 1; i <= n; i++)
    	{
    		book[i] = 0;
    	}
    	book[1] = 1;
    
    	for (i = 1; i <= n - 1; i++)
    	{
    		min = inf;
    		for (j = 1; j <= n; j++)
    		{
    			if (book[j] == 0 && dis[j] < min)
    			{
    				min = dis[j];
    				u = j;
    			}
    		}
    		book[u] = 1;
    		for (v = 1; v <= n; v++)
    		{
    			if (e[u][v] < inf)
    			{
    				if (dis[v]>dis[u] + e[u][v])
    				{
    					dis[v] = dis[u] + e[u][v];
    				}
    			}
    		}
    	}
    	printf("顶点1到各个顶点的距离分别为：->\n");
    	for (i = 1; i <= n; i++)
    	{
    		printf("%d  ", dis[i]);
    	}
    	printf("\n");
    	system("pause");
    	return 0;
    }

运行结果：

![Center 1][]

[Center]: /images/20220613/f316c91a012f45da947b2cec9242bc96.png
[Center 1]: /images/20220613/98587c46d17d4386926867201b08bc00.png