GlobalPlanner —— Dijkstra算法

navigation

Reference

• finding the shortest path with a little help

1 Introduction

Dijkstra’s algorithm can be used to determine the shortest path from one node in a graph to every other node within the same graph data structure, provided that the nodes are reachable from the starting node.

Dijkstra算法可用于确定从图中的一个节点到同一图数据结构中的其他节点的最短路径，前提是这些节点可以从起始节点到达。
该算法将继续运行，直到图中所有可达顶点都被访问，这意味着我们可以运行Dijkstra算法，找到任意两个可达节点之间的最短路径，然后将结果保存在某个地方。一旦我们只运行了一次迪杰斯特拉的算法，我们就可以一次又一次地从我们的算法中查找结果——而不必实际运行算法本身！我们唯一需要重新运行Dijkstra算法的时候是如果我们的图形数据结构发生了变化，在这种情况下，我们最终会重新运行该算法，以确保我们的特定数据结构仍然有最新的最短路径。

一个加权图如下

我们使用adjacent list来表示这个图，也可以用adjacent matrix来表示

2 Dijkstra algorithm的一些规则

• 每当我们开始访问一个新节点时，我们将首先选择已知距离/成本最小的节点进行访问。
• 一旦我们移动到将要访问的节点，我们将检查它的每个相邻节点。
• 对于每个相邻节点，我们将通过对从起始顶点到我们正在检查的节点的边的成本求和来计算相邻节点的距离/成本。
• 最后，如果到一个节点的距离/成本小于已知距离，我们将更新该顶点的最短距离。

3 Dijkstra 算法流程演示

• 建立三个数组分别存储nodes，shortest distance from start node(cost)， previous node，并进行最短距离的初始化
  
• 找到与当前节点相连的未被访问的nodes，分别计算从start node到这些相邻nodes的cost，选择cost最小的对应的那个相邻node，如果该cost比之前已知的小，那么更新这个相邻node的cost以及对应的previous node，接下来标记当前node为visited，访问这个相邻的node进行如上的迭代，until 所有的nodes都被标记为visited
  
  
  
  
  
  
  最终结果
  
  提取路径