题目

Dijkstra 算法是什么?
Dijkstra 在哪里用

提问时间：2021-03-28

答案

迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径,该算法按照最短路径长度递增的顺序产生所以最短路径.
对于图G=（V,E）,将图中的顶点分成两组：
第一组S：已求出的最短路径的终点集合（开始为{v0}）.
第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）.
算法将按最短路径长度的递增顺序逐个将第二组的顶点加入到第一组中,直到所有顶点都被加入到第一组顶点集S为止.
【算法思想】
g为用邻接矩阵表示的带权图.
（1）S