有向图（4.dijkstra算法详解）

    在图的应用中，有一个很重要的需求：我们需要知道从某一个点开始，到其他所有点的最短路径。

    这其中，Dijkstra算法是典型的最短路径算法。它的关键思想是以起始点为中心，向外一层层扩散，直到扩展到终点为止。Dijkstra算法能够得出最短路径的最优解，不过它需要遍历计算的节点相当多，所以效率不高。

    首先，用最通俗的语言解释。假定有3个顶点，A、B、C，如图：

要求A到其余各点的最短路径。很明显，A到C比A到B更短。有疑惑的是从A->B的最短距离，要么是直接A->B的边，要么是A经过C到B的边更短。我们首先找到最短的边（A->C),然后在此基础上扩展，于其余边去对比找到最小值。顶点再进一步扩充增加，按照这个思想，我们总可以找到A到所有点的最短路径。

算法描述：

    从节点1开始到其余各点的dijkstra算法，其中Wa->b表示边a->b的权，d(i)即为最短路径值，顶点集合为V={1,2,3...n}

    1.置集合S={1}，置顶点集合U={2,3,4...n}，数组d(1)=0,d(i)=W1->i（1，i之间存在边）or 无穷大（1，i之间不存在边）；

    2.在U中，令d(j)=min{d(i),i属于U}，将j从U中移至S中，若U为空集则算法结束，否则转3；

    3.对全部i属于U，如果存在边j->i,那么置d(i)=min{d(i), d(j) + Wj->i},转2

    Dijkstra算法的思想为;设G=(V, E)是一个带权有向图，把图中顶点集合V分为两部分，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有源点，以后每求出一条最短路径，就将顶点加入到S中，直到所有顶点都加入到S中，算法结束），第二组为其余未求出最短路径的顶点集合（用U表示），按最短路径的长度次序依次将第二组中的顶点加入到第一组中。

     在加入过程中，总保持着从源点v到S中各顶点的最短路径不大于从源点v到U中各顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离即为源点v到该点的最短路径长度。U中顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短距离。

算法具体步骤

    1.初始时，S中只有源点，即S = {v}，v的距离为0（到自己的距离为0）。U包含除v外地所有其他顶点，U中顶点u距离为边上的权（若v到u存在边）或 ∞ （v到u不存在边，即u不是v的出边邻接点）

    2.从U中选取一个距离v最小的顶点k加入到S中（选定的距离就是v到k的最短路径）

    3.以k为新考虑的中间点，修改U中各顶点的距离。若从源点v经过顶点k到顶点u的距离比原来距离（不经过顶点k）段，则修改顶点u的距离，修改后的距离值为顶点k的距离加上边k->u的权

    4.重复步骤2、3直到所有的顶点都加入到S中

复杂度分析：

    实现方式的不同，可能有n次或者n-1次外层的循环，这里取n次。

    步骤2每一轮的比较步骤会是n，n-1，n-2...1

    步骤3每一轮的更新步骤会是n-1，n-2...1

    这样计算出结果大致为 n²

    Dijkstra算法的时间复杂度为O(n^2)

    空间复杂度取决于存储方式，邻接矩阵为O(n^2)

再看一个例子：

算法实现：

伪代码

     Dijkstra算法解决了有向图G=(V, E)上带全的单源最短路径问题，但要求所有的边权非负）。因此，假定每条边(u，v)∈E，有w(u，v)≥0。

     Dijksra算法中设置了一个顶点集合S,从源点s到集合中的顶点的最终最短路径的权值均已确定。算法反复选择具有最短路径估计的顶点u∈V-S，并将u加入到S中，对u的所有出边进行松弛。在下面的算法实现中，用到了顶点的最小优先队列Q，排序关键字为顶点的d值。

DIJSTRA(G，w，s)

　　1　INITIALIZE-SINGLE-SOURCE(G，s)

　　2　S ← Φ

　　3　Q ← V[G]

　　4　while Q≠Φ

　　5　do u EXTRACT-MIN(Q)

　　6　S ← S∪{u}

　　7　for each vertex v∈Adj[u]

　　8　do RELAX(u，v，w)

C++代码实现

    这是前面代码中复制过来的，仍然是用模板跟容器实现的，可以做些修改使用数组或其他数据结构及实现方式。

template
int OLGraph::Dijkstra(IN const vertexNameType vertexName1)
{
int sourceIndex = getVertexIndex(vertexName1); //获取源点在容器中索引值
if (-1 == sourceIndex)
{
cerr <<"There is no vertex " <return false;
}
int nVertexNo = getVertexNumber(); //获取顶点数
vector<bool> vecIncludeArray; //顶点是否已求出最短路径
vecIncludeArray.assign(nVertexNo, false); //初始化容器
vecIncludeArray[sourceIndex] = true;
vector vecDistanceArray; //路径值容器
vecDistanceArray.assign(nVertexNo, weight(INT_MAX)); //将所有顶点到源点的初始路径值为正无穷
vecDistanceArray[sourceIndex] = weight(0); //源点到自己距离置0
vector<int> vecPrevVertex; //路径中，入边弧尾顶点编号（即指向自己那个顶点的编号）
vecPrevVertex.assign(nVertexNo, sourceIndex); //指向所有顶点的弧尾都初始为源点，源点指向所有顶点
getVertexEdgeWeight(sourceIndex, vecDistanceArray); //得到源点到其余每个顶点的距离
int vFrom, vTo;
while(1)
{
weight minWeight = weight(INT_MAX);
vFrom = sourceIndex;
vTo = -1;
for (int i = 0; i //找出还没求出最短距离的顶点中，距离最小的一个
{
if (!vecIncludeArray[i] && minWeight > vecDistanceArray[i])
{
minWeight = vecDistanceArray[i];
vFrom = i;
}
}
if (weight(INT_MAX) == minWeight) //若所有顶点都已求出最短路径，跳出循环
{
break;
}
vecIncludeArray[vFrom] = true; //将找出的顶点加入到已求出最短路径的顶点集合中
//更新当前最短路径，只需要更新vFrom顶点的邻接表即可，因为所有vFrom指向的边都在邻接表中
Edge *p = m_vertexArray[vFrom].firstout;
while (NULL != p)
{
weight wFT = p->edgeWeight;
vTo = p->headvex;
if (!vecIncludeArray[vTo] && vecDistanceArray[vTo] > wFT + vecDistanceArray[vFrom]) //当前顶点还未求出最短路径，并且经由新中间点得路径更短
{
vecDistanceArray[vTo] = wFT + vecDistanceArray[vFrom];
vecPrevVertex[vTo] = vFrom;
}
p = p->tlink;
}

}
for (int i = 0; i //输出最短路径
{
if (weight(INT_MAX) != vecDistanceArray[i])
{
cout <"->" <": ";
DijkstraPrint(i, sourceIndex, vecPrevVertex);
cout <<" " <cout <}
}
return 0;
}
template
void OLGraph::DijkstraPrint(IN int index, IN int sourceIndex, IN vector<int> vecPreVertex)
{
if (sourceIndex != index)
{
DijkstraPrint(vecPreVertex[index], sourceIndex, vecPreVertex);
}
cout <" ";
}