2. 考研
  3. 已知加权有向图G如下，回答下列问题： (1)画出该有向图G的邻接矩阵； (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

已知加权有向图G如下，回答下列问题： (1)画出该有向图G的邻接矩阵； (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。

admin2012-06-26  78
问题 已知加权有向图G如下，回答下列问题：
   
    (1)画出该有向图G的邻接矩阵；
    (2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径，并给出求解过程。
选项
答案(1)有向图G的邻接矩阵 [*] (2) [*]
解析 本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特拉(Dijk-stra)算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的基本思想是：
    (1)设置两个顶点的集合S和T=V—S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。
    (2)初始状态时，集合S中只包含源点v0，然后不断从集合T中选取到顶点b>路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点b>到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点“的最短路径长度值加上u到该顶点的路径长度值中的较小值。
    (3)此过程不断重复，直到集合T的顶点全部加入到S中为止。
转载请注明原文地址:https://kaotiyun.com/show/3fxi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

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