Dijkstra算法,又称"迪杰斯特拉算法",是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。...算法解析
1: 设置2个顶点集合S,T
S 存储已经找到的最短路径点的距离
T 存储未处理过的顶点
2: 先把起点A存储到T.准备处理
3: 获取到T的起点A,首先起点A到起点A的距离是0,直接存储到...S:A=>{length:0,route:A},
4: 然后通过起点,获取起点周围的几个点和距离,例如B距离1,C距离5,D距离3,存储到T
5: 起点到周围的点都是当前的最短路径,直接存储到S:B=>...T的E,C,E直接存储,由于C在5的时候已经存储,length为5,而A=>B length为1,B=>C length为 1,1+1{length:2...以绿色方格为起点,红色为终点,黑色为障碍物.
1: 首先绿色方格距离为0,直接存储,并获取到周围3个点(不考虑斜边和障碍物),存储到T
2: 遍历T的3个点,距离都为1,直接存储
3: 遍历3个点周围的点