首页 > 图论 > 最短路径 > Dijkstra最短路径算法[贪心]
2014
06-22

Dijkstra最短路径算法[贪心]

源最短路径问题
给定一个带权有向图 G=(V,E) ,其中每条边的权是一个非负实数。另外,还给定 V 中的一个顶点,称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

前面Bellman-Ford最短路径算法讲了单源最短路径的Bellman-Ford算法(动态规划算法)。这里介绍另外一个更常见的算法Dijkstra算法。

Dijkstra算法和 最小生成树Prim算法最小生成树算法非常类似,大家可以先熟悉下个算法。两个算法都是基于贪心算法。虽然Dijkstra算法相对来说比Bellman-Ford 算法更快,但是不适用于有负权值边的图,贪心算法决定了它的目光短浅。而Bellman-Ford 算法从全局考虑,可以检测到有负权值的回路。

这里模仿MST(Minimum Spanning Tree)的Prim算法,我们创建一个SPT(最短路径树),最初只包含源点。我们维护两个集合,一组已经包含在SPT(最短路径树)中的顶点S集合,另一组是未包含在SPT内的顶点T集合。每次从T集合中选择到S集合路径最短的那个点,并加入到集合S中,并把这个点从集合T删除。直到T集合为空为止。

举例说明,如下图所示的图:

S集合最初为空,然后选取源点0,S集合为 {0},源点到其它所有点的距离为 {0, 4, INF, INF, INF, INF, 8, INF} 。图中蓝色表示 SPT,迭代的过程如下

             

最终得到 SPT(最短路径树) 如下:

算法C++实现:

我们使用Boolean 数组sptSet[] (也有习惯用visit[]命名,表示是否访问过),来表示顶点是否为有SPT中。sptSet[v]=true,说明顶点v在SPT中。 dist[] 用来存储源点到其它所有点的最短路径。

 

#include <iostream>
#include <stdio.h>
#include <limits.h>
using namespace std;
const int V = 9; //定义顶点个数

//从未包含在SPT的集合T中,选取一个到S集合的最短距离的顶点。
int getMinIndex(int dist[V], bool sptSet[V]) {
	   int min = INT_MAX, min_index;
	   for (int v = 0; v < V; v++)
	     if (sptSet[v] == false && dist[v] < min)
	         min = dist[v], min_index = v;
	   return min_index;
}

// 打印结果
void printSolution(int dist[], int n) {
	printf("Vertex   Distance from Source\n");
	for (int i = 0; i < V; i++)
		printf("%d \t\t %d\n", i, dist[i]);
}

//source 代表源点
void dijkstra(int graph[V][V], int source) {
	int dist[V];     // 存储结果,从源点到 i的距离

	bool sptSet[V]; // sptSet[i]=true 如果顶点i包含在SPT中

	// 初始化. 0代表不可达
	for (int i = 0; i < V; i++){
		dist[i] = (graph[source][i] == 0 ? INT_MAX:graph[source][i]);
		sptSet[i] = false;
	}

	// 源点,距离总是为0. 并加入SPT
	dist[source] = 0;
	sptSet[source] = true;

	// 迭代V-1次,因此不用计算源点了,还剩下V-1个需要计算的顶点。
	for (int count = 0; count < V - 1; count++) {
		// u,是T集合中,到S集合距离最小的点
		int u = getMinIndex(dist, sptSet);

		// 加入SPT中
		sptSet[u] = true;

		//更新到V的距离。可以理解为Bellman-Ford中的松弛操作
		for (int v = 0; v < V; v++)
			if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
					&& dist[u] + graph[u][v] < dist[v])
				dist[v] = dist[u] + graph[u][v];
	}

	printSolution(dist, V);
}

int main() {
	/* 以例子中的图为例 */
	int graph[V][V] =
			{ { 0, 4, 0, 0, 0, 0, 0, 8, 0 }, { 4, 0, 8, 0, 0, 0, 0, 11, 0 }, {
					0, 8, 0, 7, 0, 4, 0, 0, 2 }, { 0, 0, 7, 0, 9, 14, 0, 0, 0 },
					{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
					{ 0, 0, 4, 0, 10, 0, 2, 0, 0 },
					{ 0, 0, 0, 14, 0, 2, 0, 1, 6 },
					{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
					{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };

	dijkstra(graph, 0);

	return 0;
}

输出源点0到其它各个顶点的最短距离:

Vertex   Distance from Source
0                0
1                4
2                12
3                19
4                21
5                11
6                9
7                8
8                14

其它

1)如果需要打印路径的话,也很简单,使用一个 parent[] 数组记录上一个节点。参考最小生成树Prim算法

2)这个是无向图的算法,有向图也类似

3)这个算法是找到所有顶点的最短路径,如果我们只需要到其中一个顶点target的最短路径,可以在循环中加一个break,当u==target即可退出。

4)Dijkstra适合图中有负权值的边。

参考:http://www.geeksforgeeks.org/greedy-algorithms-set-6-dijkstras-shortest-path-algorithm/


  1. Good task for the group. Hold it up for every yeara??s winner. This is a excellent oppotunity for a lot more enhancement. Indeed, obtaining far better and much better is constantly the crucial. Just like my pal suggests on the truth about ab muscles, he just keeps obtaining much better.

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥