我可以使用什么算法来查找图中指定节点类型之间的最短路径？

Question

这就是问题:

我有n个点(p1,p2,p3,... pn),每个点都可以以确定的成本x连接到任何其他点.

每个点属于一组点类型中的一个(例如"A""B""C""D"......).

方法的输入是我想要遵循的路径,例如"ABCADB".

输出是连接输入类型I的点的最短路径,例如"p1-p4-p32-p83-p43-p12",其中p1是A型,p4是B型,p32是C-类型,p83是A型,p43是D型,p12是B型.

"简单"的解决方案包括计算所有可能的路径,但计算成本非常高!

有人能找到更好的算法吗？

正如我在标题中所说,我不知道它是否存在!

更新:

阻止我使用Dijkstra和其他类似算法的关键点是我必须根据类型链接点.

作为输入,我有一个类型的数组,我必须按顺序链接.

这是Kent Fredric的图像(非常感谢),它描述了最初的情况(红色允许的链接)!

alt text http://img13.imageshack.us/img13/3856/immagineaol.jpg

一个真实的例子:

一个男人想早上去教堂,去餐馆,下午去博物馆.

地图上有6个教堂,30家餐厅和4个博物馆.

他希望教堂休息博物馆的距离是最小的.

Answer 1

您可以使用Floyd-Warshall算法.这是WikiPedia给出的伪代码:

/* 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] );

我不得不为一个关于同样问题的算法课程编写一个程序.这个算法就像一个魅力!祝好运.

Answer 2

有许多算法比计算所有可能的路径做得更好。 广度优先搜索是我想到的算法系列的基本起点，最佳优先搜索是合适的，因为您定义了顶点成本，如果您可以获得有关问题空间的更多信息，您也许可以使用A*或Dijkstra 算法。（在每种情况下，从允许的起始节点集中查找路径。）

重新编辑：您的路径约束（您需要满足的节点类型数组）不会阻止您使用这些算法；恰恰相反，它可以帮助他们更好地工作。您只需要以允许合并路径约束的方式实现它们，将搜索中每个步骤可用的顶点限制为给定约束的有效顶点。