路径最短算法
㈠ k最短路径算法能作为论文中的一个算法嘛
现在，我们准备介绍计算机科学史上伟大的成就之一：Dijkstra最短路径算法[1]。这个算法适用于边的长度均不为负数的有向图，它计算从一个起始顶点到其他所有顶点的最短路径的长度。在正式定义这个问题（3.1节）之后，我们讲解这个算法（3.2节）以及它的正确性证明（3.3节），然后介绍一个简单直接的实现（3.4节）。在第4章中，我们将看到这种算法的一种令人惊叹的快速实现，它充分利用了堆这种数据结构。
3.1单源最短路径问题
3.1.1问题定义
Dijkstra算法解决了单源最短路径问题。[2]
问题：单源最短路径
输入：有向图G=(V, E)，起始顶点s∈V，并且每条边e∈E的长度e均为非负值。
输出：每个顶点v∈V的dist(s,v)。
注意，dist(s,v)这种记法表示从s到v的最短路径的长度（如果不存在从s到v的路径，dist(s,v)就是+∞）。所谓路径的长度，就是组成这条路径的各条边的长度之和。例如，在一个每条边的长度均为1的图中，路径的长度就是它所包含的边的数量。从顶点v到顶点w的最短路径就是所有从v到w的路径中长度最短的。
例如，如果一个图表示道路网，每条边的长度表示从一端到另一端的预期行车时间，那么单源最短路径问题就成为计算从一个起始顶点到所有可能的目的地的行车时间的问题。
小测验3.1
考虑单源最短路径问题的下面这个输入，起始顶点为s，每个边都有一个标签标识了它的长度：
从s出发到s、v、w和t的最短距离分别是多少？
（a）0，1，2，3
（b）0，1，3，6
（c）0，1，4，6
（d）0，1，4，7
（正确答案和详细解释参见3.1.4节。）
3.1.2一些前提条件
方便起见，我们假设本章中的输入图是有向图。经过一些微小的戏剧性修改之后，Dijkstra算法同样适用于无向图（可以进行验证）。
另一个前提条件比较重要。问题陈述已经清楚地表明：我们假设每条边的长度是非负的。在许多应用中（例如计算行车路线），边的长度天然就是非负的（除非涉及时光机器），完全不需要担心这个问题。但是，我们要记住，图的路径也可以表示抽象的决策序列。例如，也许我们希望计算涉及购买和销售的金融交易序列的利润。这个问题相当于在一个边的长度可能为正也可能为负的图中寻找最短路径。在边的长度可能为负的应用中，我们不应该使用Dijkstra算法，具体原因可以参考3.3.1节。[3]
3.1.3为什么不使用宽度优先的搜索
如2.2节所述，宽度优先的搜索的一个“杀手”级应用就是计算从一个起始顶点出发的最短路径。我们为什么需要另一种最短路径算法呢？
记住，宽度优先的搜索计算的是从起始顶点到每个其他顶点的边数最少的路径，这是单源最短路径问题中每条边的长度均为1这种特殊情况。我们在小测验3.1中看到，对于通用的非负长度边，最短路径并不一定是边数最少的路径。最短路径的许多应用，例如计算行车路线或金融交易序列，不可避免地涉及不同长度的边。
但是，读者可能会觉得，通用的最短路径问题与这种特殊情况真的存在这么大的区别吗？如图3.1所示，我们不能把一条更长的边看成3条长度为1的边组成的路径吗？
图3.1路径
事实上，“一条长度为正整数
的边”和“一条由
条长度为1的边所组成的路径”之间并没有本质的区别。在原则上，我们可以把每条边展开为由多条长度为1的边组成的路径，然后应用宽度优先的搜索对图进行展开来解决单源最短路径问题。
这是把一个问题简化为另一个问题的一个例子。在这个例子中，就是从边的长度为正整数的单源最短路径问题简化为每条边的长度均为1的特殊情况。
这种简化所存在的主要问题是它扩大了图的规模。如果所有边的长度都是小整数，那么这种扩张并不是严重的问题。但在实际应用中，情况并不一定如此。某条边的长度很可能比原图中顶点和边的总数还要大很多！宽度优先的搜索在扩张后的图中的运行效率是线性时间，但这种线性时间并不一定接近原图长度的线性时间。
Dijkstra算法可以看成是在扩张后的图上执行宽度优先的搜索的一种灵活模拟，它只对原始输入图进行操作，其运行时间为近似线性。
关于简化
如果一种能够解决问题B的算法可以方便地经过转换解决问题A，那么问题A就可以简化为问题B。例如，计算数组的中位元素的问题可以简化为对数组进行排序的问题。简化是算法及其限制的研究中非常重要的概念，具有极强的实用性。
我们总是应该寻求问题的简化。当我们遇到一个似乎是新的问题时，总是要问自己：这个问题是不是一个我们已经知道怎样解决的问题的伪装版本呢？或者，我们是不是可以把这个问题的通用版本简化为一种特殊情况呢？
3.1.4小测验3.1的答案
正确答案：（b）。从s到本身的最短路径的长度为0以及从s到v的最短路径的长度为1不需要讨论。顶点w稍微有趣一点。从s到w的其中一条路径是有向边(s,w)，它的长度是4。但是，通过更多的边可以减少总长度：路径s→v→w的长度只有1+2=3，它是最短的s−w路径。类似地，从s到t的每条经过两次跳跃的路径的长度为7，而那条更迂回的路径的长度只有1+2+3=6。
3.2Dijkstra算法
3.2.1伪码
Dijkstra算法的高层结构与第2章的图搜索算法相似。[4]它的主循环的每次迭代处理一个新的顶点。这个算法的高级之处在于它采用了一种非常“聪明”的规则选择接下来处理哪个顶点：就是尚未处理的顶点中看上去最靠近起始顶点的那一个。下面的优雅伪码精确地描述了这个思路。
㈡ 最短路径算法如何选取最短的和第二短的
随便用一种最短路径算法 然后更新时先更新最短路再用最短路更新次短路
㈢ 记录所有最短路径的最短路径算法
没有一个算法是万能的
Dijkstra:单源最短路径
Floyd:每对点最短路径
SPFA(Bellmanford+队列):快速单源最短路径(可负权)
还有很多求最短路径的算法，但是归其根本，无外乎：
Label Setting和Label Correcting两大类，其实就是搜索法+动态规划。
只要灵活地掌握了搜索法、动态规划和图论，这些算法就都会了。
㈣ 最短路径算法作用
可以实现距离最短以及时间最短，从而为你节约行程的成本
㈤ 最短路径算法 Dijkstra 用C语言编出来
#include"iostream.h"
#include"stdlib.h"
#define MAXPOINT 3//定义最大的顶点数目
#define limit 32767 //设置没有路径的权代替无穷大
struct record{ //没个顶点的数据结构设置为一个数组队列
int number; //顶点号
int flag; //标志是否从队列中被选过如果为1表示选过为0表示未选
int allpath; //从源点到这个点的当前最短距离（权最小）
}path[MAXPOINT+1];
int cost[MAXPOINT+1][MAXPOINT+1]; //用来表示图的邻接矩阵
void main()
{int i,j,temp,front=1,rear=MAXPOINT,N,minnumber;
//temp表示在数组队列中的当前下标 front表示队列首 rear表示队列尾
//N 表示待输入的源点号码 minnumber 表示选中的点的号码
int min=32768; //设置一个初始值
for(i=1;i<=MAXPOINT;i++)
for(j=1;j<=MAXPOINT;j++)
{cout<<"请输入从第"<<i<<"点到第"<<j<<"点的路径长度(权)如果没有路径的话请输入'32767' "<<endl;
cin>>cost[i][j]; //初始化所有点之间的（权）路径值
}
//cout<<"请输入源点号"<<endl; //输入一个起点
//cin>>N;
for(N=MAXPOINT;N>=1;N--)//把每一个点轮流地都设置为起点，可以求出任意一对顶点之间的最短路径
{ for(i=front;i<=rear;i++) //初始化每个点的信息
{if(i==N)
path[i].allpath=0;
else
path[i].allpath=limit;
path[i].flag=0;
path[i].number=i;
}
while(rear>=1) //控制循环次数
{for(temp=front;temp<=MAXPOINT;temp++)
{ if(path[temp].allpath<min&&path[temp].flag==0)//选出一个具有最值
//的点
{ minnumber=path[temp].number;
min=path[temp].allpath ;
}
}
min=32768;
path[minnumber].flag=1;//把选中的点的标志变量置1表示已经被选过避免选中
for(i=1;i<=MAXPOINT;i++)//进行类似广度优先搜索，更新最短路径
{if((i!=minnumber)&&(path[minnumber].allpath+cost[minnumber][i]<path[i].allpath))
path[i].allpath=path[minnumber].allpath+cost[minnumber][i];
}
rear--;//次数减1
}
rear=MAXPOINT; //恢复数组以便于下一点的循环
for(j=1;j<=MAXPOINT;j++)
{ cout<<"第"<<N<<"点到第"<<j<<"点的最短路径长度（权）为";
cout<<path[j].allpath <<endl;
}
}
}
//这个程序可以求出任意一对顶点之间的最短路径，不过这种算法效率还不是很高，还有其他算法待续
㈥ 求解：图论中常见的最短路径算法有几种都是什么
主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、
㈦ 求出最短路径，要过程，用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
㈧ 求一个最短路径的算法
以前看到过，贴给你
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