问题
问答题
已知加权有向图如下图所示，回答下列问题：
试利用Dijkstra算法求上图中从顶点a到其他各顶点间的最短路径，并给出求解过程。
答案
参考答案：顶点a到其他各顶点问的最短路径的求解过程如下表所列。
解析： 本题是典型的由Dijkstra算法求出单源点的最短路径问题。迪杰斯特拉(Dijkstra)算法提出的一个按路径长度递增的次序产生最短路径的算法。算法的基本思想是：
(1)设置两个顶点的集合S和T=V-S，集合S中存放已找到最短路径的顶点，集合T存放当前还未找到最短路径的顶点。
(2)初始状态时，集合S中只包含源点v0,然后不断从集合T中选取到顶点v0路径长度最短的顶点u加入到集合S中，集合S每加入一个新的顶点u，都要修改顶点v0到集合T中剩余顶点的最短路径长度值，集合T中各顶点新的最短路径长度值为原来的最短路径长度值与顶点u的最短路径长度值加上u到该顶点的路径长度值中的较小值。
(3)此过程不断重复，直到集合T的顶点全部加入到S中为止。