C++ 图的遍历 路径搜索

C++ 图的遍历 路径搜索

两点所有连接？
把floyd算法修改一下
path初始化path[i]=[i]
for (k=1;k<=n;k++)
{
for (i=1;i {
for (j=1;j {
if (a[i,k] && a[k,j])
{
输出
path做标记
}
}
}
}
完整的算法代码肯定很长，因为还要遍历整个path数组...
我本来是学pascal的，c++语法可能有点问题
其实广度优先搜也可以，可能会比较简单，但队列是指数级增长的，所以可能会爆掉

搜索一个最优，广度扩展优先。（但是内存问题很严重，因为节点个数指数增长。）
搜索所有结果。首先要解决重复路径的问题，一般可用一个Hash函数，记录每个结点。方法当然是递归。具体怎么做，我也没写过，没遇到过这种要求。
搜索一定路径下的，所有结果，这个就好办了。优先算法就不用考虑了，优先路径找到了，也要返回继续找其它的。所以直接考虑递归所有可能。记录路径。（效率方面的话：路径很长的话，还是应该Hash并记录所遍历过的结点的状态。短的话，可以直接在搜索完后，去掉重复路径即可。）
我人懒，就不写代码了。

如果你把这张图存成邻接矩阵，直接求矩阵的n次方就可以了。最多求道矩阵的阶数那么多次。
得到的矩阵，行代表起点，列代表终点。如果a[i][j]=0表从i点到j点没有路可达。如果不为0则表示，从i到j路径长度为n（矩阵的幂）的路总共有多少条，这个是图论里的，你可以去看看。
求矩阵的幂可以用二分矩阵。

重赏之下必有勇夫

啊。。。。帅哥。。。我终于看懂你说的意思了。。。。两点间第K短路
构造A*函数H*(X) = H(X) + G(X)
先做一遍最短路——Dijkstra
利用广搜不断扩展
具体实现不说了。。。。好长
你去搜。。好多好多
启发式搜索，设置状态为，X.v 当前状态的顶点，X.w 当前状态的路径长度。由于此图可以重复走点，所以每个状态都不一样，不用判重。估价函数H为该点到终点的最短路，由于H=H*，所以肯定是相容的。然后A*搜索，每次搜到终点就记录，直到记录了K次后就是第K短路了。