c语言算法 - 贪婪算法 - 单源最短路径

核心提示：1. 数据结构的选择我们需要为未到达的顶点列表L选择一个数据结构，从L中可以选出d 值最小的顶点，c语言算法 - 贪婪算法 - 单源最短路径(2)，如果L用最小堆（见9 . 3节）来维护，则这种选取可在对数时间内完成，即使改变邻接表，也只会使最后一个f o r循环的总时间降为O ( e )（因为只有与i 邻接的顶点的d

1. 数据结构的选择

我们需要为未到达的顶点列表L选择一个数据结构。从L中可以选出d 值最小的顶点。如果L用最小堆（见9 . 3节）来维护，则这种选取可在对数时间内完成。由于3) 的执行次数为O ( n )，所以所需时间为O ( n l o g n )。由于扩充一条边产生新的最短路径时，可能使未到达的顶点产生更小的d 值，所以在4) 中可能需要改变一些d 值。虽然算法中的减操作并不是标准的最小堆操作，但它能在对数时间内完成。由于执行减操作的总次数为： O(有向图中的边数)= O ( n2 )，因此执行减操作的总时间为O ( n2 l o g n )。

若L用无序的链表来维护，则3) 与4) 花费的时间为O ( n2 )，3) 的每次执行需O(|L | ) =O( n )的时间，每次减操作需( 1 )的时间（需要减去d[j] 的值，但链表不用改变）。利用无序链表将图1 - 11的伪代码细化为程序1 3 - 5，其中使用了C h a i n (见程序3 - 8 )和C h a i n I t e r a t o r类（见程序3 - 1 8）。

程序13-5 最短路径程序

template
void AdjacencyWDigraph::ShortestPaths(int s, T d[], int p[])
{// 寻找从顶点s出发的最短路径, 在d中返回最短距离
// 在p中返回前继顶点
if (s < 1 || s > n) throw OutOfBounds();
Chain L; // 路径可到达顶点的列表
ChainIterator I;
// 初始化d, p, L
for (int i = 1; i <= n; i++){
d[i] = a[s][i];
if (d[i] == NoEdge) p[i] = 0;
else {p[i] = s;
L . I n s e r t ( 0 , i ) ; }
}
// 更新d, p
while (!L.IsEmpty()) {// 寻找具有最小d的顶点v
int *v = I.Initialize(L);
int *w = I.Next();
while (w) {
if (d[*w] < d[*v]) v = w;
w = I.Next();}
// 从L中删除通向顶点v的下一最短路径并更新d
int i = *v;
L . D e l e t e ( * v ) ;
for (int j = 1; j <= n; j++) {
if (a[i][j] != NoEdge && (!p[j] ||
d[j] > d[i] + a[i][j])) {
// 减小d [ j ]
d[j] = d[i] + a[i][j];
// 将j加入L
if (!p[j]) L.Insert(0,j);
p[j] = i;}
}
}
}

若N o E d g e足够大，使得没有最短路径的长度大于或等于N o E d g e，则最后一个for 循环的i f条件可简化为：if (d[j] > d[i] + a[i][j])) NoEdge 的值应在能使d[j]+a[i][j] 不会产生溢出的范围内。

2. 复杂性分析

程序1 3 - 5的复杂性是O ( n2 )，任何最短路径算法必须至少对每条边检查一次，因为任何一条边都有可能在最短路径中。因此这种算法的最小可能时间为O ( e )。由于使用耗费邻接矩阵来描述图，仅决定哪条边在有向图中就需O ( n2 )的时间。因此，采用这种描述方法的算法需花费O ( n2 )的时间。不过程序1 3 - 5作了优化（常数因子级）。即使改变邻接表，也只会使最后一个f o r循环的总时间降为O ( e )（因为只有与i 邻接的顶点的d 值改变）。从L中选择及删除最小距离的顶点所需总时间仍然是O( n2 )。