首页 > 代码库 > Dijkstra算法——通过边实现松弛

Dijkstra算法——通过边实现松弛

算法思想:每次找到离源点最近的顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径.时间复杂度是O(N^2).

基本步骤:

  1. 将所有的顶点分为两部分,已知最短路程的顶点集合S和未知最短路径的顶点集合V. 最开始,已知最短路径在集合S中只有源点一个顶点,用book数组来标记哪些点在集合S中.
  2. 设置源点p到自己的最短路径为0(即dis[p] = 0). 若存在有源点能直接到达的顶点i,则把dis[i] 设为 e[p][i]. 同时把所有其他(源点不能直接到达的)顶点的最短路径设为∞.
  3. 在集合V的所有顶点中选择一个离源点p最近的顶点u(即dis[u]最小)加入到集合P中. 并考察所有以点u为起点的边,对每一条边进行松弛操作.
  4. 重复第3步,如果集合V为空,则结束,最终得到的dis数组中的值就是源点到所有顶点的最短路径.
一个点到其余各个顶点的最短路径也叫做“单源最短路径”. 这个Dijkstra同样求最短路径的图同样不能有负权边,因为扩展到负权边的时候会产生更短的路径,有可能破坏了已经更新的点路径不会改变的性质.


Code:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define INF 999999
int book[10];          /// 用来纪录已经是最短路径的点

int main(int argc, char const *argv[])
{
	int i, j, m, n;
	int q1, q2, q3;
	int u, v, min;
	int e[100][100], dis[10];

	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;
			}
		}
	}

	for(i = 1; i <= m; ++i)
	{
		scanf("%d %d %d", &q1, &q2, &q3);
		e[q1][q2] = q3;
	}

	for(i = 1; i <= n; ++i)
	{
		dis[i] = e[1][i];
	}

	book[1] = 1;              /// Dijkstra 算法核心
	for(i = 1; i < n; ++i)      /// 计算n-1次
	{
		min = INF;
		for(j = 1; j <= n; ++j)
		{
			if(dis[j] < min && book[j] == 0)
			{
				min = dis[j];
				u = j;
			}
		}


		book[u] = 1;
		for(v = 1; v <= n; ++v)
		{
			if(e[u][v] != INF && dis[v] > dis[u] + e[u][v])
			{
				dis[v] = dis[u] + e[u][v];            /// 这个过程就是"松弛"
			}
		}
	}

	for(i = 1; i <= n; ++i)
	{
		printf("%d ", dis[i]);
	}
	printf("\n");

	system("pause");
	return 0;
}


Dijkstra算法——通过边实现松弛