【算法】图的最短路径(Dijkstra算法)

逃离我推掉我的手 2022-06-08 03:59 283阅读 0赞

今天要总结的是图的迪杰斯特拉算法。这个算法是针对有**向带权图**的，求的是**图中某一个定点到其余所有顶点的最短路径**。

下面说说这个算法的基本思想吧：设定两个集合A和B，A中存放我们已经处理过的顶点，B中存放图中剩余顶点。刚开始的时候，A中只有一个我们选定的起点v0，每一次从集合B中取到v0的代价最小的点并入，每一次并入时都需要修改v0到B中顶点的代价，直到所有的顶点都并入为止。

算法准备：

1、数组dist，用于存放v0到图中个顶点的代价，数组下标表示顶点编号

2、数组path，用于存放路径，数组下标表示顶点编号，下标所对应的数组值表示能够到达当前这个顶点的前一个顶点编号，最后连起来就是v0到图中各顶点的最短路径了。如果没有前前驱顶点，则内容值为-1。

3、数组set，用于标识图中顶点是否被处理过，数组下标表示顶点编号。处理过为1，没处理过为0。

4、使用图的邻接矩阵来存储有向带权图，graph\[i\]\[j\]。

算法过程（我们选择编号为0的顶点作为起点）：

1、首先进行3个数组的初始化，把set数组全部初始化为0；dist数组全部初始化为无穷大，path数组全部初始化为-1。

2、将set\[0\]的值设置为1，然后遍历邻接矩阵的第0行，依次更新dist数组的每一项。

3、将dist数组中值不为无穷大的在path中的对应下标，把它们的值改为0。因为编号为0的点是它们的前驱嘛。如下图：

![20170914091735522][]

4、选择dist数组中值最小的点的下标，这里为1。

5、将set\[1\]的值设置为1

6、遍历邻接矩阵的第1行(因为1是最小权值的下标)，将dist\[1\]的值与邻接矩阵graph\[1\]\[i\]的值相加（此时是以编号为1的点作为中间点，看看由v0->v1再到其余点的路径长度会不会比v0直接到它们的路径长度短），如果这个值比dist\[i\]的值小，就更新dist\[i\]，同时将path\[i\]的值设置为1，执行这个操作的前提是，set\[i\]为0。操作完成后如下图：

![20170914092731172][]

7、重复【4】~【6】步，如果已经处理过的点就不用再判断了。直到set数组全变为1。最后如下图

![20170914093705513][]

现在，我们就可以看出最短路径了。

比如v0到v6的路径为，注意path数组，从下标6的位置开始看起，逐级向上查找，直到遇到-1为止

v6->v4->v5->v2->v1->v0

有没有发现这个是逆序的呢？根据后进先出的原则，我们想到输出要用到栈。

下面上代码：

1、首先是图的结构体定义

#define Max 100
    typedef struct graph *Graph;
    typedef struct graph
    {
    	int data[30][30];
    	int n , e;
    }graph;

2、接下来就是算法核心代码

void Dijkstra(Graph g , int v , int path[] , int dist[])
    {
    	int set[Max];
    	//initial
    	int i , j;
    	for(i = 0 ; i < g->n ; i++)
    	{
    		set[i] = 0;
    		dist[i] = g->data[v][i];
    		if(g->data[v][i] < Max)
    		{
    			path[i] = v;
    		}
    		else
    		{
    			path[i] = -1;
    		}
    	}
    
    	set[0] = 1;
    	path[0] = -1;
    	//main
    
    	for(i = 1 ; i<= g->n-1 ; i++)
    	{
    		int min = Max;
    		int minP = 0;
    		for(j = 0 ; j < g->n ; j++)
    		{
    			if(set[j] == 0 && dist[j] < min)
    			{	
    				min = dist[j];
    				minP = j;
    			}
    		}
    
    		set[minP] = 1;
    		for(j = 0 ; j < g->n ; j++)
    		{
    			if(set[j] == 0 && g->data[minP][j] + min < dist[j])
    			{
    				dist[j] = g->data[minP][j] + min;
    				path[j] = minP;
    			}
    		}
    	}
    }

注：a、参数列表中的变量v就是我们指定的定点。

b、在初始化path数组的过程中，如果某个顶点在邻接矩阵v行的值不为无穷大，说明该点可以由v到达，所以将该path数组中的值设置成v，而在矩阵中v行值为无穷大的，就设置成-1。

3、输出路径代码

void showPath(int path[], int begin)
    {
    	int stack[Max];
    	int top = -1;
    	int i = begin;
    	int flag = 0;
    	while(path[begin] != -1)
    	{
    		stack[++top] = begin;
    		begin = path[begin];
    	}
    	stack[++top] = begin;
    	if(top == 0)
    	{
    		printf("v%d 无最短路径",stack[top]);
    		return;
    	}
    	while(top != -1)
    	{
    		if(!flag)
    		{
    		   printf("v%d",stack[top]);
    		   flag++;
    		}
    		else
    			printf("->v%d",stack[top]);
    		top--;
    	}
    }

如果没有最短路径的话，说明这个点就没有前驱了，都是-1，在路径序列中只有它自己。

[20170914091735522]: /images/20220608/52459b99f72f404b81ee92e4ecf25bca.png
[20170914092731172]: /images/20220608/a52461658fbf4b2cacec18d061d9b4e3.png
[20170914093705513]: /images/20220608/66ce1ec0ae7942bfb1a08c1a5332dfb1.png