我正在尝试在Matlab中实现Dijkstra算法，用于查找具有节点约束的最短路径。具体地说，我想强制路径通过一组给定的节点。
我有一个邻接矩阵作为输入，我需要一个函数，以开始节点，结束节点和约束作为一个数组。该算法还应该能够处理多个约束并快速执行。
Exemple for a graph
这里A和E之间的最短路径是7A ⇒B⇒E，但是我想得到A和E之间经过C的最短路径。Ideadly我想一个算法，可以找到两个节点之间的最短路径，并通过一个或多个节点。
谁能解释一下如何修改Dijkstra的算法来处理这些约束，并帮助我在Matlab中实现？
谢谢大家！
1条答案
按热度按时间yh2wf1be1#
由于路径需要经过C，先找出A和C之间的最短路径，再找出C和B之间的最短路径，然后将它们组合起来。
你可以通过检查节点顺序的所有可能性来使用任意数量的约束来做到这一点，这至少需要O（n！），用于n个约束。
对于任何数量的节点作为约束的更一般的解决方案，创建一个仅包含A，B和这些节点的新图，然后使用访问图中所有节点的算法。
更多信息here