2. 考研
  3. 带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条，在找到一条最短路径的同时，还需要输出不同最短路径的条数。现有一种解决该问题的方法： (1)初始化结点集合S为仅包含源结点s

带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条，在找到一条最短路径的同时，还需要输出不同最短路径的条数。现有一种解决该问题的方法： (1)初始化结点集合S为仅包含源结点s

admin2014-12-08  50
问题 带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。若最短路径不止一条，在找到一条最短路径的同时，还需要输出不同最短路径的条数。现有一种解决该问题的方法：
    (1)初始化结点集合S为仅包含源结点s；用一个整型数组Counter[v]来记录从结点s到结点v的最短路径的条数；各结点Counter的初始值为0。
    (2)从未加入S的结点中选择当前距离最小的结点v(“当前距离”是指从s到v且仅经过S中结点的最短距离)，将其加入S。
    (3)对每个与v相邻的结点w，若w不在S内，检查：    ①若v的加入使得w的当前距离变小，则更新w的当前距离为(v，w)的边长与v的当前距离之和，并日．令Counter[w]=1。    ②若v的加入是s到w的长度相同的另一条最短路径，则Counter[w]++；
    (4)重复步骤(2)和(3)，直到所有结点都被收录到集合S中。    若该方法可行，请证明之；否则，请举例说明。
选项
答案首先，该算法是错误的。图8一10给出了反例：设图中各边长为1，则从s到w有3条长度棚同的路径，而使用此算法得到的结果为2。 [*] 问题出现在以下3个地办： (1)当v的加入产生新的最短路径时，从s到v再到w的最短路径条数等于v的最短路径条数，而不是仅等于1。所以步骤(3)中①的Counter[w]=1 应改为等于Counter[w]=Counter[v]。 (2)若v的加入是s到w的长度相同的另一条最短路径，则w的最短路径条数并不是仅增加了1，而是v带过来的所有最短路径。所以(3)中②的Counter[w]++改为(Counter[w]+=Couter[v]。 (3)根据前两步的修改，Counter[s]的初始值必须为1，而不是0，否则后面所有结点的Counter都会一直是0。 总结：此题属于对经典Dijkstra算法的推广应用，类似题目还有累积所有长度相同的最短路径上的结点个数等，其实现原理相同。另一类相似的推广应用是找到包含边数最少的那条最短路径，这时题干中算法的第(3)步应该改为以下步骤。 对每个与v相邻的结点w，若w不在S内，检查： ①若v的加入使得w的当前距离变小，则更新w的当前距离为(v，w)的边长与v的当前距离之和，更新Counter[w]=Counter[v]+1，并将v记录在w的路径上。 ②若v的加入是s到w的长度相同并且边数更少(Counter[w]＞Counter[v]+1)的另一条最短路径，则Counter[w]=Counter[v]+1，并将v记录在w的路径上。 这里的整型数组Counter[v]记录从s结点到v结点的最短路径包含的边数，各结点Counter的初始值均为0。此问题很容易出错的地方是当发现另一条长度相同但包含边数更少的最短路径时，只更新了Counter，却忘记了更新w的路径。 类似的题目还有求包含最多边的最短路径，或者给每个结点赋予价值，求价值最高的最短路径等，其实现原理相同。
解析
转载请注明原文地址:https://kaotiyun.com/show/xZxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)