人工智能/搜索/迪杰斯特拉算法
迪杰斯特拉算法用于图搜索。它是最佳的，这意味着它将找到最短的路径。它是无信息的，这意味着它不需要在事先知道目标节点。事实上，它找到了从每个节点到源节点的最短路径。迪杰斯特拉算法有很多可能的变化，针对特定目的进行了优化。一个例子是，如果已知目标节点，算法可以被指示一旦找到该节点的最短路径就终止。迪杰斯特拉算法可以被认为是一种启发式搜索，类似于贪婪搜索，如果搜索有一个已知目标，并且可以被认为是一种穷举搜索，当搜索没有目标节点并且所有节点都被考虑时。迪杰斯特拉算法的效率使其成为网络路由协议的最佳选择。由于本质上任何组合优化问题都可以被表述为最短路径问题，因此迪杰斯特拉算法对于人工智能研究也很重要。
迪杰斯特拉算法需要一个源节点来开始。它将找到从该源节点到所有其他节点的最短距离。对于每个节点，它需要内存来存储一个距离值和一个标记节点已访问或未访问的标志。它还需要一个指针来跟踪当前节点。
- 将源节点分配为距离值零，并将所有其他节点分配为距离值无穷大。
- 将所有节点标记为未访问，并将源节点设置为当前节点。
- 对于当前节点，考虑其所有未访问的邻居，并使用经过当前节点的路径计算其与源节点的距离。如果通过包含当前节点的路径计算出的未访问邻居的距离小于其距离值，则使用新值覆盖距离值。
- 当当前节点的所有邻居都被考虑后，将当前节点标记为已访问。已访问的节点将永远不会再次被检查，其值是最终的，也是最小的。
- 将具有最低距离值的未访问节点设置为当前节点，并从步骤 3 继续。
（本节直接取自维基百科）在以下算法中，代码 u := node in Q with smallest dist[]，搜索具有最小 dist[u] 值的顶点集 Q 中的顶点 u。该顶点从顶点集 Q 中移除并返回给用户。dist_between(u, v) 计算两个相邻节点 u 和 v 之间的长度。第 11 行的 alt 是从根节点到相邻节点 v 的路径的长度，如果它要经过 u。如果这条路径比 v 当前记录的最短路径短，则用这条 alt 路径替换当前路径。previous 数组填充了一个指向源图上“下一个跃点”节点的指针，以获得到源节点的最短路线。
1 function Dijkstra(Graph, source):
2 for each vertex v in Graph: // Initializations
3 dist[v] := infinity // Unknown distance function from source to v
4 previous[v] := undefined // Previous node in optimal path from source
5 dist[source] := 0 // Distance from source to source
6 Q := the set of all nodes in Graph
// All nodes in the graph are unoptimized - thus are in Q
7 while Q is not empty: // The main loop
8 u := vertex in Q with smallest dist[]
9 if dist[u] = infinity:
10 break // all remaining vertices are inaccessible
11 remove u from Q
12 for each neighbor v of u: // where v has not yet been removed from Q.
13 alt := dist[u] + dist_between(u, v)
14 if alt < dist[v]: // Relax (u,v,a)
15 dist[v] := alt
16 previous[v] := u
17 return previous[]
如果我们只对顶点 source 和 target 之间的最短路径感兴趣，则如果 u = target，我们可以在线 10 终止搜索。现在，我们可以通过迭代读取从 source 到 target 的最短路径
1 S := empty sequence 2 u := target 3 while previous[u] is defined: 4 insert u at the beginning of S 5 u := previous[u]
现在序列 S 是构成从 target 到 source 的最短路径之一的顶点列表，或者如果不存在路径则为空序列。
一个更普遍的问题是找到 source 和 target 之间的所有最短路径（可能存在多个具有相同长度的不同路径）。然后，而不是在 previous[] 的每个条目中只存储单个节点，而是存储满足松弛条件的所有节点。例如，如果 r 和 source 都连接到 target，并且它们都位于通过 target 的不同最短路径上（因为两种情况下的边成本相同），那么我们将 r 和 source 都添加到 previous[target] 中。当算法完成时，previous[] 数据结构实际上将描述一个图，它是原始图的子集，其中一些边已删除。它的关键属性是，如果算法以某个起始节点运行，则从该节点到新图中任何其他节点的任何路径将是原始图中这些节点之间的最短路径，并且原始图中所有具有该长度的路径都将存在于新图中。然后，为了实际找到这两个给定节点之间的所有这些短路径，我们将使用一种路径查找算法在新图上，例如深度优先搜索。
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest 和 Clifford Stein。算法导论，第二版。麻省理工学院出版社和麦格劳-希尔，2001。 ISBN 0-262-03293-7。第 24.3 节：迪杰斯特拉算法，第 595-601 页。
- 维基百科 (2009/03/11)。 http://en.wikipedia.org/wiki/Dijkstra's_algorithm
- 迪杰斯特拉算法再探：OR/MS 连接 (2009/04/11)。 http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra_new/index.html