Dijkstra 算法
用英语：
这是一种寻找从 A 点到 B 点的最短路径的算法。
在计算方面，我们将路径简化为由节点和弧组成的图。每个节点代表一个中间点，而每条弧连接两个节点，并具有一个（非负）权重，表示在两个节点之间遍历的成本。
要实现该算法，您需要两个列表：
- 完成：一组（节点，成本），您已经计算了要达到的最低成本。
- 工作：已检查的（节点，成本）的排序列表。
算法：
working.addNode(Start, 0); // No cost to get to start.
for( (node, cost) = working.popHead(); node != End; (node,cost) = working.popHead())
{
// If we have already processed this node ignore it.
if (finished.find(node))
{ continue;
}
// We have just removed a node from working.
// Because it is the top of the list it is guaranteed to be the shortest route to
// the node. If there is another route to the node it must go through one of the
// other nodes in the working list which means the cost to reach it will be higher
// (because working is sorted). Thus we have found the shortest route to the node.
// As we have found the shortest route to the node save it in finished.
finished.addNode(node,cost);
// For each arc leading from this node we need to find where we can get to.
foreach(arc in node.arcs())
{
dest = arc.dest();
if (NOT (finished.find(dest)))
{
// If the node is already in finished then we don't need to worry about it
// as that will be the shortest route other wise calculate the cost and add
// this new node to the working list.
destCost = arc.cost() + cost;
working.addNode(dest,destCost); // Note. Working is sorted list
}
}
}
所以如果你考虑一下这个算法。假设您从伦敦前往曼彻斯特。
finished = {} // empty.
working = { (London,0) }
使用以下成本矩阵：
L S O B N M W
(L) ondon - 50 60 100 130 - -
(S) outhampton 50 - 70 - - - -
(O) xford 60 70 - 50 - 200 -
(B) irmingham 100 - 50 - - 80 110
(N) orwich 130 - - - - - -
(M) anchester - - 200 80 - - 80
Ne(W) castle - - - 110 - 80 -
现在，您将伦敦从工作列表中取出（因为它位于首位）并将其放入已完成列表中。然后将与伦敦直接相连的所有城镇添加到工作列表中。
finished = { (London,0) }
working = { (Southampton, 50), (Oxford, 60), (Birmingham, 100), (Norwich,130) }
考虑工作环境中的城镇是从伦敦扩大的泡沫的外缘。Dijkstra 算法的工作是不断扩大泡沫，直到我们到达曼彻斯特（不追溯我们已经采取的任何步骤）。所以气泡总是向外膨胀，我们总是把气泡中最小的那部分膨胀。
所以下一步是占据列表的头部并重复。从南安普敦出发，只有两个目的地。回到伦敦（我们将其丢弃在完成的列表中）和牛津。到牛津的费用是 50 + 从南安普顿到牛津的费用（所以请注意它两次在工作列表中，但不要担心，我们稍后会因为不是最佳路线而放弃它）。
finished = { (London,0), (Southampton,50) }
working = { (Oxford, 60), (Birmingham, 100), (Oxford, 120), (Norwich,130) }
所以重复循环。榜首是牛津。从牛津出发，我们可以去曼彻斯特（200）、伯明翰（50）或返回伦敦（60）或南安普顿（请记住，我们需要将到达牛津的费用加到上面的每一项费用中。请注意，从牛津出发，我们可以去了南安普敦，但我们已经找到了到南安普敦的最短路线，因此不需要处理）这将为我们留下：
finished = { (London,0), (Southampton,50), (Oxford, 60) }
working = { (Birmingham, 100), (Birmingham,110), (Oxford, 120), (Norwich,130), (Manchester,200)}
请注意，我们现在在工作列表中有曼彻斯特（这是我们的目的地）。但是我们需要继续努力，因为我们可能会找到一条更短的路线。所以现在我们从伯明翰扩展。从那里我们可以去牛津（50），曼彻斯特（80），伦敦（100），纽卡斯尔（110）。首先加上去伯明翰的费用，这给了我们：
finished = { (London,0), (Southampton,50), (Oxford, 60), (Birmingham, 100) }
working = { (Birmingham,110), (Oxford, 120), (Norwich,130), {Manchester, 180), (Manchester,200), (Newcastle, 210)}
接下来的两个节点。牛津和伯明翰已经在完成列表中，所以我们可以忽略它们。因此，除非从诺里奇到曼彻斯特的路线少于 50 英里，否则我们将在之后的迭代中到达曼彻斯特。