求一寻路算法

各位高人,小弟求一寻路算法.万望指点一下.

如下:
有ABCDEF六个城市,AB互通,AC互通,AD互通,BC互通,CE互通.DE互通,EF互通,其他之间都不能直接到达.
假设两个互通的城市之间的距离都是一样的(为1).

求一算法,要求从任意城市到另一个城市之间.希望能算出最短路径,及最短路径长度.

我自己思考了一下,用矩阵,多叉树都未能想明白.看了一下A星算法,但我又没弄明白这怎么建矩阵.如果考虑城市之间的距离的话又怎么弄呢?
望各位高人能给小弟指点一下.希望能给小弟说出算法名字,原理,要是有C/C++原代码那就更加感激不尽了...

8 个解决方案

#1

你这是图论的东西。看数据结构去吧。

#2

参考这个吧，floyd算法，在原来基础上加入"保存所有路径"
http://baike.baidu.com/view/14495.htm

#3

是图论。

#4

WARSHELL!!! 虽然实现起来有点复杂不过还是不错的算法

#5

很简单哈。。比如把6个城市存在图中，int g[6][6]; 初始化为最大值(比如INT_MAX)，并把互通的设为1。

for (i = 0; i < 6; ++i)
for (j = 0; j < 6; ++j)
for (k = 0; k < 6; ++k) {
       if (g[j][k] > g[j][i] + g[i][k] && g[j][i] != INT_MAX && g[i][k] != INT_MAX) {
                g[j][k] = g[j][i] + g[i][k];
                next[j] = i;
       }
}
就这个样子吧。。。满简单的。。。。
关于证明，看看算法导论就可以了。。

#6

谢谢各位,我参考二楼给出的算法,已经解决了问题,再次感谢各位,马上结贴,人人有分哈.

#7

你先把图自己画出来，然后看一下。你会发现很简单的。
先找出能够两地之间的所有路径，然后在此基础上找到最短的就行了

#8

我建议你去学一下桥的原理,可能你就会知道点什么.

#1