最短路径(Dijkstra算法)

Dijkstra算法

一个点到其余个点的算法

仍用邻接矩阵的方法存储图
使用dis[]初始化为：存储1号顶点到其余顶点的初始路径
此时dis数组的值被称为最短路径的估计值

松弛

算法的基本思想：
每次找到离源点最近的一个顶点，然后以该顶点为中心开始扩展，最终得到源点到其余所有点的最短路径。
基本步骤如下：


算法核心代码：

for (i = 1; i <= n; i++)
{
	dis[i] = e[1][i];	//对dis进行初始化
}
for (i = 1; i <= n; i++)
{
	book[i] = 0;	//book数组用来标记1到i点是否已经是最小路径
}
book[1] = 1;

//Dijksta算法核心语句
for (i = 1; i <= n; 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])	//如果1到v点的现在的最短距离
			{								//小于
				dis[v]=dis[u]+e[u][v]		//经过u点儿到达v点的距离，则更新1到v点的最短路径
			}
		}
	}
}

Dijkstra算法的时间复杂度为O(N²)
每次找到距离顶点最近的那个顶点的时间复杂度为O(N)
可以用堆来优化，使其时间复杂度降低为O(logN)
对于边数M少于N²的稀疏图来说，可以用邻接表来存储图
使得时间复杂度变为O(M+N)logN
当然，这时的最坏情况下，M就是N²，这样(M+N)logN要比N²大，但通常情况下，不会有那么多边，因次(M+N)logN比N²小很多

使用邻接表存储图

//u,v,w数组大小的设置要比m的最大值还要大1
int first[5], next[5];
//first、next数组大小要比n的最大值还要大1
scanf("%d%d", &n, &m);
//n是顶点数，m是边数
for (i = 1; i <= n; i++)
{
	first[i] = -1;	//初始化fisrt数组为-1，表示1~n顶点都没有边
}
for (i = 1; i <= n; i++)
{
	scanf("%d%d%d", &u[i], &v[i], &w[i]);
	//核心
	next[i] = first[u[i]];
	first[u[i]] = i;
}

为每个点设置一个链表，里面保存了从顶点i出发的所有边

首先，我们对每一条边进行1~m编号。
用u，v和w三个数组来记录每条边的信息，u存储边的始点，v存储边的终点，w存储边的权值
first的1~n号单元格存储1到n号顶点的第一条边的编号，初始化的时候因为没有边加入所有都是-1
first[u[i]]保存顶点u[i]的第一条边的编号
next[i]存储编号为i的边的下一条边的编号

对于存储于邻接表的边的遍历
在找到1号顶点的第一条边之后，剩下的边都可以在next数组中找到

int n, m, i;
int u[6], v[6], w[6];
k = first[1];	//找到1号顶点的第一条边
while (k != -1)	//当不是空边的时候
{
	printf("%d %d %d\n", u[k], v[k], w[k]);
	k = next[k];	//找该边的下一条边
}

此时遍历某个顶点的边的时候的遍历顺序正好与读入时候的顺序相反
因为，在为每个顶点插入边的时候都是直接插入"链表"的首部，而不是尾部

遍历每个顶点的边：

for (i = 1; i <= n; i++)
{
	k = first[i];	//选择顶点
	while (k != -1)	//从顶点开始，遍历从该点可以到达的边
	{
		printf("%d %d %d\n", u[k], v[k], w[k]);
		k = next[k];
	}
}

用邻接表来存储图的时间空间复杂度为O(M)
遍历每一条边的时间复杂度是O(M)
因此，用邻接表存储稀疏图是比用邻接矩阵来存储好很多。

Dijkstra的缺点

不能用于带有负权边的图
因为扩展到负权边的时候会产生更短的路径，有可能就破坏了已经更新的点路程不会改变的性质