这就是问题：
我有 n 个点（p1、p2、p3、.. pn），每个点都可以以确定的成本 x 连接到任何其他点。
每个点都属于一组点类型中的一个（例如“A”“B”“C”“D”...）。
该方法的输入是我想要遵循的路径，例如“A-B-C-A-D-B”。
输出是连接我在输入中给出的类型的点的最短路径，例如“p1-p4-p32-p83-p43-p12”，其中p1是A型，p4是B型，p32是C型型，p83 为 A 型，p43 为 D 型，p12 为 B 型。
“简单”的解决方案包括计算所有可能的路径，但计算成本非常高！
有人能找到更好的算法吗？
正如我在标题中所说，我不知道它是否存在！
Update:
阻止我使用 Dijkstra 和其他类似算法的关键点是我必须根据类型链接点。
作为输入，我有一个类型数组，我必须按该顺序链接。
这是肯特·弗雷德里克（Kent Fredric）的图像（非常感谢），它描述了初始情况（红色允许链接）！
一个现实生活中的例子：
一个人想早上参观教堂，去餐馆，最后下午参观博物馆。
地图上有 6 座教堂、30 家餐厅和 4 家博物馆。
他希望教堂-休息区-博物馆的距离尽可能小。
您可以使用 Floyd–Warshall 算法。这是维基百科给出的伪代码：
/* Assume a function edgeCost(i,j) which returns the cost of the edge from i to
(infinity if there is none).
Also assume that n is the number of vertices and edgeCost(i,i)=0
*/
int path[][];
/* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
from i to j using intermediate vertices (1..k-1). Each path[i][j] is initialized to
edgeCost(i,j) or infinity if there is no edge between i and j.
*/
procedure FloydWarshall ()
for k: = 1 to n
for each (i,j) in {1,..,n}2
path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
我必须为同一问题的算法课程编写一个程序。这个算法很有魅力！祝你好运。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
