求最短路径的算法
‘壹’ 求最短路径算法
java">importjava.awt.*;
importjava.util.HashSet;
importjava.util.Random;
classexample2{
privatestaticPoint[]mTestPoints;
//已知平面上N点坐标,求遍历所有点的最短路径.
publicstaticvoidmain(String[]args){
//两点之间的距离d=√(a^2+b^2)其中a=|x1–x2|;b=|y1-y2|
//都是简单的正相关函数,距离最短那么需要a+b最小
//n个点需要求C(n,2)次
//其实java提供了两点之间距离的Api咱们直接使用即可
generateTestPoints();
doubleminDistance=Double.MAX_VALUE;
for(inti=0;i<mTestPoints.length;i++){
//两两计算,数组中每个点只跟后面的点求距离
for(intj=i+1;j<mTestPoints.length;j++){
doubledistance=mTestPoints[i].distance(mTestPoints[j]);
if(distance<minDistance){
minDistance=distance;
}
}
}
//得到结果
System.out.println("最短距离为:"+minDistance);
}
(){
//随机生成10个点的集合,为了去重使用hashSet
Randomrandom=newRandom();
HashSet<Point>mPointSet=newHashSet<>();
for(inti=0;i<10;i++){
booleanadd=mPointSet.add(newPoint(random.nextInt(100),random.nextInt(100)));
if(!add){
--i;
}
}
mTestPoints=mPointSet.toArray(newPoint[10]);
}
}
‘贰’ 最短路径算法
Dijkstra算法，A*算法和D*算法
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。
大概过程：
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。
提高Dijkstra搜索速度的方法很多，常用的有数据结构采用Binary heap的方法，和用Dijkstra从起始点和终点同时搜索的方法。
A*（A-Star)算法是一种启发式算法，是静态路网中求解最短路最有效的方法。
公式表示为： f(n)=g(n)+h(n),
其中f(n) 是节点n从初始点到目标点的估价函数，
g(n) 是在状态空间中从初始节点到n节点的实际代价，
h(n)是从n到目标节点最佳路径的估计代价。
保证找到最短路径（最优解的）条件，关键在于估价函数h(n)的选取：
估价值h(n)<= n到目标节点的距离实际值，这种情况下，搜索的点数多，搜索范围大，效率低。但能得到最优解。
如果 估价值>实际值, 搜索的点数少，搜索范围小，效率高，但不能保证得到最优解。
估价值与实际值越接近，估价函数取得就越好。
例如对于几何路网来说，可以取两节点间欧几理德距离（直线距离）做为估价值，即f=g(n)+sqrt((dx-nx)*(dx-nx)+(dy-ny)*(dy-ny))；这样估价函数f在g值一定的情况下，会或多或少的受估价值h的制约，节点距目标点近，h值小，f值相对就小，能保证最短路的搜索向终点的方向进行。明显优于Dijstra算法的毫无无方向的向四周搜索。
conditions of heuristic
Optimistic (must be less than or equal to the real cost)
As close to the real cost as possible
主要搜索过程：
创建两个表，OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
遍历当前节点的各个节点，将n节点放入CLOSE中，取n节点的子节点X,->算X的估价值->
While(OPEN!=NULL)
{
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点) break;
else
{
if(X in OPEN) 比较两个X的估价值f //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于OPEN表的估价值 )
更新OPEN表中的估价值; //取最小路径的估价值
if(X in CLOSE) 比较两个X的估价值 //注意是同一个节点的两个不同路径的估价值
if( X的估价值小于CLOSE表的估价值 )
更新CLOSE表中的估价值; 把X节点放入OPEN //取最小路径的估价值
if(X not in both)
求X的估价值;
并将X插入OPEN表中; //还没有排序
}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; //实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。
}
A*算法和Dijistra算法的区别在于有无估价值，Dijistra算法相当于A*算法中估价值为0的情况。
动态路网，最短路算法 D*A* 在静态路网中非常有效（very efficient for static worlds），但不适于在动态路网，环境如权重等不断变化的动态环境下。
D*是动态A*（D-Star,Dynamic A*） 卡内及梅隆机器人中心的Stentz在1994和1995年两篇文章提出，主要用于机器人探路。是火星探测器采用的寻路算法。
主要方法：
1.先用Dijstra算法从目标节点G向起始节点搜索。储存路网中目标点到各个节点的最短路和该位置到目标点的实际值h,k（k为所有变化h之中最小的值,当前为k=h。每个节点包含上一节点到目标点的最短路信息1(2),2(5),5(4)，4（7）。则1到4的最短路为1-2-5-4。
原OPEN和CLOSE中节点信息保存。
2.机器人沿最短路开始移动，在移动的下一节点没有变化时，无需计算，利用上一步Dijstra计算出的最短路信息从出发点向后追述即可，当在Y点探测到下一节点X状态发生改变，如堵塞。机器人首先调整自己在当前位置Y到目标点G的实际值h(Y)，h(Y)=X到Y的新权值c(X,Y)+X的原实际值h(X).X为下一节点(到目标点方向Y->X->G），Y是当前点。k值取h值变化前后的最小。
3.用A*或其它算法计算，这里假设用A*算法,遍历Y的子节点，点放入CLOSE,调整Y的子节点a的h值，h(a)=h(Y)+Y到子节点a的权重C(Y,a),比较a点是否存在于OPEN和CLOSE中，方法如下：
while()
{
从OPEN表中取k值最小的节点Y;
遍历Y的子节点a,计算a的h值 h(a)=h(Y)+Y到子节点a的权重C(Y,a)
{
if(a in OPEN) 比较两个a的h值
if( a的h值小于OPEN表a的h值 )
{ 更新OPEN表中a的h值;k值取最小的h值
有未受影响的最短路经存在
break;
}
if(a in CLOSE) 比较两个a的h值 //注意是同一个节点的两个不同路径的估价值
if( a的h值小于CLOSE表的h值 )
{
更新CLOSE表中a的h值; k值取最小的h值;将a节点放入OPEN表
有未受影响的最短路经存在
break;
}
if(a not in both)
将a插入OPEN表中; //还没有排序
}
放Y到CLOSE表；
OPEN表比较k值大小进行排序；
}
机器人利用第一步Dijstra计算出的最短路信息从a点到目标点的最短路经进行。
D*算法在动态环境中寻路非常有效，向目标点移动中，只检查最短路径上下一节点或临近节点的变化情况，如机器人寻路等情况。对于距离远的最短路径上发生的变化，则感觉不太适用。
‘叁’ 迪杰斯特拉算法求最短路径题怎么做
最早的路径题，这个在做的时候，你可以通过练习一个函数关系式就能够进行，把它简单的测量出来的还是比较简单的。
‘肆’ Flody算法 求最短路径的求解过程
你好。
很幸运看到你的问题。
但是又很遗憾到现在还没有人回答你的问题。也可能你现在已经在别的地方找到了答案，那就得恭喜你啦。
可能是你问的问题有些专业了，没人会。或者别人没有遇到或者接触过你的问题，所以帮不了你。建议你去问题的相关论坛去求助，那里的人通常比较多，也比较热心，可能能快点帮你解决问题。
希望我的回答也能够帮到你！
祝你好运~！
‘伍’ 求一个最短路径的算法
以前看到过，贴给你
Private Function OrderXY(X() As Double, Y() As Double)
Dim i, j, k, m, n, num, temp As Double
Dim NewX() As Double
Dim NewY() As Double
Dim Smin As Double '定义最短总距离
If UBound(X()) <> UBound(Y()) Then MsgBox "坐标错误": Exit Function '防止数据错误
n = UBound(X())
ReDim p(n) As Long
p(0) = 0: num = 1
For i = 1 To n
p(i) = i 'p()数组依次存储从0到n共n+1个数
num = num * i '计算num，num表示的是n个坐标（除X(0),Y(0)以外)共有n！种排列
Next
ReDim Stance(num - 1) As Double '定义数组存储每种连接方法的总距离
ReDim NewX(n)
ReDim NewY(n)
For i = 0 To n - 1 'Stance（0）是按照原坐标顺序依次连接的总距离
Stance(0) = Stance(0) + Sqr((Y(i + 1) - Y(i)) * (Y(i + 1) - Y(i)) + (X(i + 1) - X(i)) * (X(i + 1) - X(i)))
Next
Smin = Stance(0)
For k = 0 To n
NewX(k) = X(k)
NewY(k) = Y(k)
Next
i = n - 1
'下面对p()数组的n个数（除0以外）进行排列，每产生一种排列方式，坐标数组的数据就对应交换，并计算这一路径的总距离
Do While i > 0
If p(i) < p(i + 1) Then
For j = n To i + 1 Step -1 '从排列右端开始
If p(i) <= p(j) Then Exit For '找出递减子序列
Next
temp = p(i): p(i) = p(j): p(j) = temp '将递减子序列前的数字与序列中比它大的第一个数交换
temp = X(i): X(i) = X(j): X(j) = temp '与之对应的X Y也交换
temp = Y(i): Y(i) = Y(j): Y(j) = temp
For j = n To 1 Step -1 '将这部分排列倒转
i = i + 1
If i >= j Then Exit For
temp = p(i): p(i) = p(j): p(j) = temp
temp = X(i): X(i) = X(j): X(j) = temp
temp = Y(i): Y(i) = Y(j): Y(j) = temp
Next
m = m + 1
For k = 0 To n - 1
Stance(m) = Stance(m) + Sqr((Y(k + 1) - Y(k)) * (Y(k + 1) - Y(k)) + (X(k + 1) - X(k)) * (X(k + 1) - X(k)))
Next
If Stance(m) <= Smin Then
Smin = Stance(m)
For k = 0 To n
NewX(k) = X(k): NewY(k) = Y(k)
Next
End If
i = n
End If
i = i - 1
Loop
For k = 0 To n
X(k) = NewX(k): Y(k) = NewY(k)
Next '此时的X（） Y（） 就按照最短路径排列
End Function
‘陆’ 求出最短路径，要过程，用Dijkstra算法。。。
从v1开始遍历
v2 = 2;
v3 = 5;
v2较小所以跳到v2
v3 = 4;
v4 = 6;
v5 = 8;
v3较小所以跳到v3
v4 = 5;
v6 = 7;
v4较小所以跳到v4
v6 = 6;
v7 = 9;
v6较小所以跳到v6
v7 = 8;
所以最后结果v1 -> v7最短路径为v1->v2->v3->v4->v6->v7,最短路径长度为8
‘柒’ 求！最短路径算法 Dijkstra 用C语言编出来
Dijkstra算法--c++源代码--by
伟伟猪
[转贴
2005-12-15
20:21:00
]
发表者:
伟伟猪
/***********************************************
设G=(V,E)是一个每条边都有非负长度的有向图，有一个特异的顶点s称为缘。
单源最短路径问题，或者称为最短路径问题，是要确定从s到V中没一个其他
顶点的距离，这里从顶点s到x的距离定义为从s到x的最短路径问题。这个问题
可以用Dijkstra算法解决。下面我给我了c++下的源代码！
--by
伟伟猪
************************************************/
#include<iostream.h>
void
main()
{
int
infinity=100,j,i,n,k,t,**w,*s,*p,*d;
cout<<"input
the
value
of
n:";
cin>>n;
cout<<endl;
d=new
int[n];
s=new
int[n];
p=new
int[n];
w=new
int*[n];
for(i=0;i<n;i++)
{w[i]=new
int[n];}
for(i=0;i<n;i++)
for(j=0;j<n;j++)
cin>>w[i][j];
for(s[0]=1,i=1;i<n;i++)
{
s[i]=0;d[i]=w[0][i];
if(d[i]<infinity)
p[i]=0;
else
p[i]=-1;
}
for(i=1;i<n;i++)
{
t=infinity;k=1;
for(j=1;j<n;j++)
if((!s[j])&&(d[j]<t))
{t=d[j];k=j;}
s[k]=1;//point
k
join
the
S
for
(j=1;j<n;j++)
if((!s[j])&&(d[j]>d[k]+w[k][j]))
{d[j]=d[k]+w[k][j];p[j]=k;}
}
cout<<"从源点到其它顶点的最短距离依次如下：";
for(i=1;i<n;i++)
cout<<d[i]<<"
";
}
/*********
顶点个数用n表示，这里给出的例子n=6
100
1
12
100
100
100
100
100
9
3
100
100
100
100
100
100
5
100
100
100
4
100
13
15
100
100
100
100
100
4
100
100
100
100
100
100
具体例子见
电子工业出版社
《算法设计技巧与分析》148页
************/
‘捌’ 最短路径算法 C语言
#include<stdio.h>
#defineMAXNODE108
intpath[MAXNODE+1][MAXNODE+1]={0};
intmain(void)
{
FILE*fpr,*fpw;
intva,vb,i,j,k;
fpr=fopen("in.txt","r");/*读取的文件名称in.txt*/
fpw=fopen("out.txt","w");/*path的数据在out.txt中展现*/
while(fscanf(fpr,"%d%d",&va,&vb)!=EOF)
path[va][vb]=path[vb][va]=1;
for(k=1;k<=MAXNODE;++k){
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(!path[i][k]||!path[k][j])
continue;
if(!path[i][j])
path[i][j]=path[i][k]+path[k][j];
elseif(path[i][j]>path[i][k]+path[k][j])
path[i][j]=path[i][k]+path[k][j];
}
}
}
for(i=1;i<=MAXNODE;++i){
for(j=1;j<=MAXNODE;++j){
if(i==j)
fprintf(fpw,"%-10d",0);
elseif(path[i][j])
fprintf(fpw,"%-10d",path[i][j]);
else
fprintf(fpw,"%-10d",-1);
}
fprintf(fpw," ");
}
return0;
}
注意：floyd算法中k为最外层，这是动态规划的思想，不能改变i,j,k的顺序！！！
这是之前的答案的错误之处。
-1表示不通。
具体程序分析，我可以加你QQ，愿意的话，你把QQ写给我。
‘玖’ 最短路径法如何计算
最短路径算法有三种，Floyd，dijkstra，Bellman_Ford。其中，Floyd适合用于计算每两点间的路径，dijkstra适合稀疏图，bellman则适合稠密图中的已知起点终点，计算最短路径的问题。时间复杂度，floyd算法为n立方，dijk为n平方，bellman为n平方，其中n是点数。dijk可用堆维护，时间复杂度可减至nlogn，而bellman可用队列维护，此方法于1994年被国人提出，命名比较土鳖叫SPFA(shortest path faster algorithm。。。)。至于如何计算，有了名字，搜一下就ok。
‘拾’ 求解：图论中常见的最短路径算法有几种都是什么
主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、