山寨机中的战斗机！	程序优化工程师到底对IT界有没有贡献

最短路径

楼主finix（*_*）2002-03-05 12:39:57 在 VC/MFC / 基础类提问

在一张有上万个点的有向图上，查找指定两点的最短路径，各位大虾有没有好的办法？
如果使用邻接矩阵会不会费内存？问题点数：50、回复次数：33Top

1 楼Flysnow（飞雪）回复于 2002-03-05 12:43:12 得分 0

上万个点，不管用什么算法，都肯定会费内存Top

**2 楼finix（_）**回复于 2002-03-05 12:45:52 得分 0

能否提供一些算法的思路Top

3 楼morningsing（奈何）回复于 2002-03-05 12:52:10 得分 0

你可以参考计算机网络协议中的最短路径算法，其实并不麻烦Top

4 楼myctx（Neo）回复于 2002-03-05 12:53:39 得分 10

用Dijkstra算法，当然用的辅助空间还是比较多的，至少需要一个二维树组，两个一维数组，还有邻接矩阵。

也可以用Floyd算法，用的空间更多，当你可以把所有顶点间的最短路径都一次性算出来，然后存在哪里，把原来的不用的空间释放掉，这样查询的速度也会加快。Top

**5 楼finix（_）**回复于 2002-03-05 12:57:12 得分 0

有没有详细介绍Dijkstra floye算法的资料，谢谢！Top

6 楼lithe（）回复于 2002-03-05 13:06:11 得分 0

关注Top

7 楼ericzhangali（另一个空间）回复于 2002-03-05 13:17:05 得分 10

如果是上万个点的话，估计过时间复杂度吗？很可怕的。
这已经是不可解问题了。
用遗传算法。Top

**8 楼finix（_）**回复于 2002-03-05 13:23:59 得分 0

何谓遗传算法？好恐怖！
详细一点好吗？
Top

9 楼complayer（顽石）回复于 2002-03-05 13:34:54 得分 0

可以把数据放在数据库中，Oracle的查询速度很快的。
我们建了上海的主干道路网最短路径查询，然后用Oracle存储过程实现。
最慢也不会超过30秒。
Oracle存储过程根本不成问题。Top

10 楼myctx（Neo）回复于 2002-03-05 13:48:01 得分 0

的确，如果上万个点的话，每次都查是太慢的，

应该考虑用数据库解决。Top

11 楼ericzhangali（另一个空间）回复于 2002-03-05 13:48:01 得分 0

对于工程和科学中的许多实际问题，找到最优解是很困难的。
因为精确求解的计算量是与问题的规模成指数型增长的。而找到一个最优解的唯一可靠方法是穷举法，即搜索问题的整个参变量空间。
然而在许多情况下，由于参变量空间太大，以致在限定的时间内只可能搜索其中极小的一部分，传统的优化算法在搜索过程中容易陷入局部最优，尤其是所定义的适应函数是复杂多维的、不连续的、非规则的或有噪声的。
遗传算法是一种概率搜索算法，是一类随机算法，但它不是简单的随机走动，它可以有效地利用已有的信息来搜寻那些有希望改善解质量的串。
Top

12 楼myctx（Neo）回复于 2002-03-05 13:51:28 得分 0

很难吧Top

13 楼ericzhangali（另一个空间）回复于 2002-03-05 13:54:30 得分 0

这就好象是货郎担问题，组合优化领域中的一个典型问题，涉及求多个变量的函数的最小值。虽然它陈述起来简单，但求解却很困难，它一直是运筹学中最富挑战性的问题之一。
由于其可能的路径条数是随着点的数目n成指数型增长的，例如，一个12个城市的货郎担问题具有39916800（=11！）条不同的路径，这类组合优化问题称之为NP完全问题。它们的精确求解的计算量是与问题的规模n成指数型地增长的。
一般来说，对于一个中等规模的问题，例如n=100，则应用现存的计算机就已不可能求出它的真正最小值了。故人们探索它们的近似解法，遗传算法也属此类。Top

14 楼ericzhangali（另一个空间）回复于 2002-03-05 13:56:39 得分 0

用数据库就能解决吗？首先就得算出数据，这就是一个NP完全问题了，再就是保存的空间复杂度了。Top

15 楼hz1101（lake）回复于 2002-03-05 14:07:42 得分 0

用Dijkstra算法，对于4千多个节点，每次计算两节点间的最短路径时不会超过0.05秒(赛扬330，128M内存),我做过多次实验的。Top

**16 楼finix（_）**回复于 2002-03-05 14:19:20 得分 0

给我看看原程序好吗？finix@citiz.netTop

17 楼totalindex（洪清）回复于 2002-03-05 14:24:42 得分 0

用Dijkstra算法，在清华大学出版的《数据结构》中有C++实现，很简单。Top

18 楼idoloveyou（从高二开始上CSDN的人现在都工作了）回复于 2002-03-05 22:54:48 得分 0

没有权值得话用Warshall！！！
我最爱用！！！
只需要4个循环变量和一个2位数组！Top

19 楼thomas269（Thomas）回复于 2002-03-05 23:06:43 得分 0

finix (finix): 係咪要Dijkstra - The shortest path算法呀! 我有呀!
C Source CodeTop

20 楼thomas269（Thomas）回复于 2002-03-05 23:16:26 得分 0

發了啦!Top

21 楼king_koo（向东）回复于 2002-03-06 08:33:22 得分 0

Thomas：我又要啊~
king_koo@163.netTop

22 楼fflucy（）回复于 2002-03-06 08:53:56 得分 0

可否也给我一份：zyflucy@sina.comTop

23 楼david5307（david）回复于 2002-03-06 09:00:16 得分 0

:)
Top

**24 楼finix（_）**回复于 2002-03-06 10:20:13 得分 0

各位大虾，有没有使用邻接表来做最短路径的啊？上万各点的邻接矩阵的存储空间太大了！Top

25 楼csdn_cloud（拔光毛的兔兔）回复于 2002-03-06 10:27:01 得分 0

Thomas：我又要啊~
tec_cloud@sohu.comTop

26 楼power168（）回复于 2002-03-06 10:34:44 得分 10

给你一篇摘录文章参考参考

最短路径算法源码(VB)

　　本人载网站开发gis,游自编的最短路径查询程序，速度特快，3万节点，35000条路全部遍历，只需1秒。现将最短路径的思路告诉大家，希望大家在优化，并用不同语言编制，我正在学delphi,准备用delphi做成库，本例以由拓扑关系的arc/info 文件为数据源。其中a1,b1,c1是以fnode排序生成的数组，a1对应fnode,b1对应tnode,c1对应length,同样a2,b2,c2,是以tnode 生成的数组。Indexa1是对应某一起点与其相连的终点的个数，indexb1时对应某一终点与其相连的起点的个数，即其拓扑关系。
Public Function shortpath(startno As Integer, endno As Integer) As Single
以开始点，结束点为参数。
Dim result() As Single
Dim result1 As Integer
定义结果点
Dim s1 As Single
Dim min As Single
Dim ii, i, j, aa As Integer
Dim yc() As Boolean
Dim ycd() As Boolean
Dim rs1() As Single
Dim no() As Integer
Dim nopoint As Integer
ReDim yc(1 To maxno) As Boolean
ReDim ycd(1 To maxno) As Boolean
ReDim rs1(1 To maxno) As Single
ReDim result(1 To 2, 1 To maxno) As Single
定义结果，其中result(1,maxno)为结果点，result(2,maxno)为结果长度。
For i = 1 To maxno// maxno为网中最大的节点数。
yc(i) = False //标记已经查过的点。
ycd(i) = False //标记已经作结果点用过的点
rs1(i) = 1E+38 //假设从起点到任一点的距离都为无穷大
Next i
ll = startno //设置开始点。
yc(ll) = True //标记开始点为真。即已经作结果点用过。
j = 0
For aa = 1 To maxno
先从与开始点相连的终点寻找
For i = 1 To indexa1(2, ll) //以与ll点相连的起点的个数循环
result1 = b1(indexa1(1, ll) - i + 1)找出与LL点相连的终点的点号
s1 = c1(indexa1(1, ll) - i + 1) + result(2, ll)找出长度并求和
If yc(result1) = True Then GoTo 200如果以被经查过进行下一个
If ycd(result1) = True Then//如果已经作为结果点判断哪一个长
If rs1(result1) >= s1 Then//如果这一点到起点的长度比现在的路线长，替代
rs1(result1) = s1
result(1, result1) = ll//设置到这点的最短路径的前一点为LL点（精华部分）
result(2, result1) = s1设置到这点的最短路径长度
GoTo 200
Else
GoTo 200
End If
End If
如果上面的条件都不符合则进行下面的语句
ycd(result1) = True
rs1(result1) = s1
result(1, result1) = ll
result(2, result1) = s1
每找到一个点加一，为了下面的判断
j = j + 1
ReDim Preserve no(1 To j) As Integer
从新定义数组并使其值为当前的点号
no(j) = result1
200 Next I
再从与开始点相连的终点寻找，与上面一样不再标注
For i = 1 To indexb2(2, ll)
result1 = a2(indexb2(1, ll) - i + 1)
s1 = c2(indexb2(1, ll) - i + 1) + result(2, ll)
If yc(result1) = True Then GoTo 300
If ycd(result1) = True Then
If rs1(result1) >= s1 Then
rs1(result1) = s1
result(1, result1) = ll
result(2, result1) = s1
GoTo 300
Else
GoTo 300
End If
End If
ycd(result1) = True
rs1(result1) = s1
result(1, result1) = ll
result(2, result1) = s1
j = j + 1
ReDim Preserve no(1 To j) As Integer
no(j) = result1
300 Next I

设置最小为无穷大，最短路径点为空
min = 1E+38
minpoint = Null
（优化部分）
找出已经查过点中长度最短的点
For i = aa To j
If min > rs1(no(i)) Then
ii = i
min = rs1(no(i))
minpoint = no(i)
End If
Next I
如果没有结果，即起点与终点没有通路退出程序
If min = 1E+38 Then Exit Function
（重点优化）将两点互换，减少循环。
no(ii) = no(aa)
no(aa) = minpoint
标记已经作为结果点判断过
yc(minpoint) = True
ll = minpoint
判断结果点是否等于终点，如果等于则已经找到最短路径
If minpoint = endno Then Exit For
Next aa
返回最短路径长度
Stpath = result(2, endno)
End Function
Top

27 楼mjm_d（菠萝蜜多）回复于 2002-03-06 13:23:50 得分 0

上万个点，靠，我算40×40个在PIII上用了两分，上万个估计可以用银河了，笑Top

28 楼kickmaster1（忘情天师天师被封杀！？）回复于 2002-03-06 13:43:55 得分 0

我用C++做的
3万多个点，只用0.5秒，
很快。

Top

**29 楼finix（_）**回复于 2002-03-06 16:12:34 得分 0

用dijkstra吗？给我看看吧！Top

30 楼Justin（兰色梧桐）回复于 2002-03-06 16:27:01 得分 0

这是我做算法设计作业时留下的一个Dijkstra算法例子，20个点

/*
* File: shortest.c
* Description: Shortest Path Dijkstra Algorithm
* Created: November 26, 2001
* Author: Justin Hou (B990614108)
*
*/

#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* Infinity */
#define N 20 /* Vertex number */

int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* store current shortest distance */
int v0 = 'A' - 65; /* begin at A */

void main()
{
int final[N], i, v, w, min;

for (v = 0; v < N; v++) /** Initialize **/
{
final[v] = false;
dist[v] = cost[v0][v]; /* init current shortest distance */
}
final[v0] = true;

for (i = 0; i < N-1; i++) { /** Search the other N-1 vertexes **/
min = I; /* current minimum */
for (w = 0; w < N; w++) /* search the minimum vertex */
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
final[v] = true; /* new vertex join in */

for (w = 0; w < N; w++) /* update dist[] data */
if (!final[w] && dist[v] + cost[v][w] < dist[w])
dist[w] = dist[v] + cost[v][w];
}

for (i = 0; i < N; i++) /** Display the result on screen **/
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}Top

31 楼Justin（兰色梧桐）回复于 2002-03-06 16:29:44 得分 10

这是我做的20结点的Dijkstra算法求最短路径的例子。

/*
* File: shortest.c
* Description: Shortest Path Dijkstra Algorithm
* Created: November 26, 2001
* Author: Justin Hou (B990614108)
*
*/

#include <stdio.h>
#define true 1
#define false 0
#define I 9999 /* Infinity */
#define N 20 /* Vertex number */

int cost[N][N] = {
{0,3,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I,I,I},
{3,0,5,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I,I,I},
{I,5,0,4,I,I,I,1,I,I,I,I,I,I,I,I,I,I,I,I},
{I,I,4,0,2,I,I,I,6,I,I,I,I,I,I,I,I,I,I,I},
{I,I,I,2,0,I,I,I,I,7,I,I,I,I,I,I,I,I,I,I},
{1,I,I,I,I,0,1,I,I,I,2,I,I,I,I,I,I,I,I,I},
{I,6,I,I,I,1,0,6,I,I,I,7,I,I,I,I,I,I,I,I},
{I,I,1,I,I,I,6,0,2,I,I,I,3,I,I,I,I,I,I,I},
{I,I,I,6,I,I,I,2,0,8,I,I,I,4,I,I,I,I,I,I},
{I,I,I,I,7,I,I,I,8,0,I,I,I,I,5,I,I,I,I,I},
{I,I,I,I,I,2,I,I,I,I,0,4,I,I,I,3,I,I,I,I},
{I,I,I,I,I,I,7,I,I,I,4,0,3,I,I,I,4,I,I,I},
{I,I,I,I,I,I,I,3,I,I,I,3,0,3,I,I,I,5,I,I},
{I,I,I,I,I,I,I,I,4,I,I,I,3,0,7,I,I,I,2,I},
{I,I,I,I,I,I,I,I,I,5,I,I,I,7,0,I,I,I,I,3},
{I,I,I,I,I,I,I,I,I,I,3,I,I,I,I,0,5,I,I,I},
{I,I,I,I,I,I,I,I,I,I,I,4,I,I,I,5,0,8,I,I},
{I,I,I,I,I,I,I,I,I,I,I,I,5,I,I,I,8,0,6,I},
{I,I,I,I,I,I,I,I,I,I,I,I,I,2,I,I,I,6,0,4},
{I,I,I,I,I,I,I,I,I,I,I,I,I,I,3,I,I,I,4,0}
};
int dist[N]; /* store current shortest distance */
int v0 = 'A' - 65; /* begin at A */

void main()
{
int final[N], i, v, w, min;

for (v = 0; v < N; v++) /** Initialize **/
{
final[v] = false;
dist[v] = cost[v0][v]; /* init current shortest distance */
}
final[v0] = true;

for (i = 0; i < N-1; i++) { /** Search the other N-1 vertexes **/
min = I; /* current minimum */
for (w = 0; w < N; w++) /* search the minimum vertex */
if (!final[w] && dist[w] < min) {
min = dist[w];
v = w;
}
final[v] = true; /* new vertex join in */

for (w = 0; w < N; w++) /* update dist[] data */
if (!final[w] && dist[v] + cost[v][w] < dist[w])
dist[w] = dist[v] + cost[v][w];
}

for (i = 0; i < N; i++) /** Display the result on screen **/
printf("%c->%c: %2d\t", v0 + 65, i + 65, dist[i]);
}Top

32 楼ericzhangali（另一个空间）回复于 2002-03-06 16:29:59 得分 10

to kickmaster1(忘情天师天师被封杀！？) ：
我很怀疑的提供的数据，请问你对三万多个点做些什么事儿？
我怀疑你0.5秒算的东西是不是预期的东西。Top

33 楼ericzhangali（另一个空间）回复于 2002-03-06 16:34:39 得分 0

想问问如果用你的程序求解一个非常著名的Grötschel的442个顶点的货郎担问题（给定了每个顶点的坐标）求出的近似最优解是多少，用多少时间？Top

34 楼kickmaster1（忘情天师天师被封杀！？）回复于 2002-03-06 16:56:58 得分 0

交通公路的路径查询，
查出起点终点和经过的弧段长度和弧段号Top