复杂的路径

Question

                      L->|
  A -> B              ^  |
  |__> C -> D-> G->X--|  |
       K    |_> T  |  |_>Z
       |___________|

我希望这个小图有助于传达我想要做的事情.

我有一个包含7,000个位置的列表,每个位置都有一个未定义但门数较少的门.每扇门都是两个位置之间的桥梁.

参考上面的图表,我将如何找到通过门从A到Z的最快路线？

我不需要完整源代码,只需伪装代码即可.

显然你可以采取A - > B - > C - > D - > G - > X - > L - > Z,但最短路径是A - > B - > C - > K - > X - > Z.

Answer 1

将您的位置表示为节点,将门表示为图形中的边.然后应用一些相当标准的最短路径算法,你就完成了.