最短路径算法

㈠ 图论中常见的最短路径算法有几种都是什么

主要是有三种、、
第一种是最直接的贪心dijkstra算法、、可以利用堆数据结构进行优化、、缺点就是不能求有负权的最短路与判断负环、、
第二种是bellman-ford算法、、根据松弛操作的性质是可以来判断负环的、、时间复杂度是O(nm)的、、
第三种是SPFA算法、、把他单独拿出来作为一种算法并不是非常好的、、他的实质应该是上面的bellman-ford算法的队列优化时间复杂度更低、O(KE)、K的值约等于2、、

㈡ 求一个最短路径的算法

以前看到过，贴给你
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

㈢ "最短路径优先算法"的优缺点

这个算法一般出现在网络中，用于路由器的路由寻址，我也只了解这方面的优缺点。如果不对，LZ就别看了。
所谓最短路径，实际上说的是跳数。比如从一条路走会经过三个路由器，而从另一条路走，会经过两个路由器，那么此算法会判断2跳比3跳要短，但具体每一跳会花多长时间，经过多长路程，它不会考虑的。所以不一定算法的最短路径就是真实的最短。因为很多因素算法没有考虑，比如通信质量，网线长度……
C语言我只看过一个模拟现实的例子，大概是说公车走什么路线长度最短，那个算法考虑的是路线的长短，而不是跳数，优点当然就是路线的绝对最短，缺点就是没考虑到其他现实因素，比如是否堵车（相当于网络通信质量）之类。
总之不管什么算法，考虑到的因素就是它的优点，反过来说，缺点往往就是算法忽略的因素。
补充一下，如果说的不是算法本身的优劣，而是细节的实现方面，那就是从时间复杂度和空间复杂度两个方面去考虑了，希望对LZ有用。

㈣ 最短路径法如何计算

最短路径算法有三种，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 最短路径算法的一种高效率实现*

随着计算机的普及以及地理信息科学的发展，GIS因其强大的功能得到日益广泛和深入的应用。网络分析作为GIS最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用，而网络分析中最基本最关键的问题是最短路径问题。最短路径不仅仅指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。相应地，最短路径问题就成为最快路径问题、最低费用问题等。由于最短路径问题在实际中常用于汽车导航系统以及各种应急系统等（如110报警、119火警以及医疗救护系统），这些系统一般要求计算出到出事地点的最佳路线的时间应该在1 s～3 s内，在行车过程中还需要实时计算出车辆前方的行驶路线，这就决定了最短路径问题的实现应该是高效率的。其实,无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。经典的最短路径算法——Dijkstra算法是目前多数系统解决最短路径问题采用的理论基础，只是不同系统对Dijkstra算法采用了不同的实现方法。
据统计，目前提出的此类最短路径的算法大约有17种。F.Benjamin Zhan等人对其中的15种进行了测试，结果显示有3种效果比较好，它们分别是：TQQ（graph growth with two queues）、DKA (the Dijkstra's algorithm implemented with approximate buckets) 以及 DKD (the Dijkstra�s algorithm implemented with double buckets )，这些算法的具体内容可以参见文献〔1〕。其中TQQ算法的基础是图增长理论，较适合于计算单源点到其他所有点间的最短距离；后两种算法则是基于Dijkstra的算法，更适合于计算两点间的最短路径问题〔1〕。总体来说，这些算法采用的数据结构及其实现方法由于受到当时计算机硬件发展水平的限制，将空间存储问题放到了一个很重要的位置，以牺牲适当的时间效率来换取空间节省。目前，空间存储问题已不是要考虑的主要问题，因此有必要对已有的算法重新进行考虑并进行改进，可以用空间换时间来提高最短路径算法的效率。
1 经典Dijkstra算法的主要思想
Dijkstra算法的基本思路是：假设每个点都有一对标号 (dj, pj)，其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短路径中j点的前一点。求解从起源点s到点j的最短路径算法的基本过程如下：
1) 初始化。起源点设置为：① ds=0, ps为空;② 所有其他点: di=∞, pi= ;③ 标记起源点s，记k=s,其他所有点设为未标记的。
2) 检验从所有已标记的点k到其直接连接的未标记的点j的距离，并设置：
dj=min〔dj, dk+lkj〕
式中，lkj是从点k到j的直接连接距离。
3) 选取下一个点。从所有未标记的结点中，选取dj 中最小的一个i：
di=min〔dj, 所有未标记的点j〕
点i就被选为最短路径中的一点，并设为已标记的。
4) 找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设置：
i=j*
5) 标记点i。如果所有点已标记，则算法完全推出，否则，记k=i，转到2) 再继续。
2 已有的Dijkstra算法的实现
从上面可以看出，在按标记法实现Dijkstra算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所述算法的2)～5)步。这是一个循环比较的过程，如果不采用任何技巧，未标记点将以无序的形式存放在一个链表或数组中。那么要选择一个权值最小的弧段就必须把所有的点都扫描一遍，在大数据量的情况下，这无疑是一个制约计算速度的瓶颈。要解决这个问题，最有效的做法就是将这些要扫描的点按其所在边的权值进行顺序排列，这样每循环一次即可取到符合条件的点，可大大提高算法的执行效率。另外，GIS中的数据 (如道路、管网、线路等)要进行最短路径的计算，就必须首先将其按结点和边的关系抽象为图的结构，这在GIS中称为构建网络的拓扑关系 (由于这里的计算与面无关，所以拓扑关系中只记录了线与结点的关系而无线与面的关系，是不完备的拓扑关系)。如果用一个矩阵来表示这个网络，不但所需空间巨大，而且效率会很低。下面主要就如何用一个简洁高效的结构表示网的拓扑关系以及快速搜索技术的实现进行讨论。
网络在数学和计算机领域中被抽象为图，所以其基础是图的存储表示。一般而言，无向图可以用邻接矩阵和邻接多重表来表示，而有向图则可以用邻接表和十字链表〔4〕 表示，其优缺点的比较见表 1。
表 1 几种图的存储结构的比较
Tab. 1 The Comparsion of Several Graph for Storing Structures
名 称 实现方法 优 点 缺 点 时间复杂度
邻接矩阵 二维数组 1. 易判断两点间的关系 占用空间大 O(n2+m*n)
2. 容易求得顶点的度
邻接表 链表 1. 节省空间 1. 不易判断两点间的关系 O(n+m)或O(n*m)
2. 易得到顶点的出度 2. 不易得到顶点的入度
十字链表 链表 1. 空间要求较小 结构较复杂 同邻接表
2.易求得顶点的出度和入度
邻接多重表 链表 1. 节省空间 结构较复杂 同邻接表
2. 易判断两点间的关系

目前,对于算法中快速搜索技术的实现，主要有桶结构法、队列法以及堆栈实现法。TQQ、DKA 以及 DKD 在这方面是比较典型的代表。TQQ虽然是基于图增长理论的，但是快速搜索技术同样是其算法实现的关键，它用两个FIFO的队列实现了一个双端队列结构来支持搜索过程〔1〕。
DKA和DKD是采用如图 1 所示的桶结构来支持这个运算，其算法的命名也来源于此。在DKA算法中，第i个桶内装有权值落在 〔b*i, (i+1)*b) 范围内的可供扫描的点，其中b是视网络中边的权值分布情况而定的一个常数。每一个桶用队列来维护，这样每个点有可能被多次扫描，但最多次数不会超过b次。最坏情况下，DKA的时间复杂度将会是O(m*b+n(b+C/b))，其中，C为图中边的最大权值。DKD将点按权值的范围大小分装在两个级别的桶内，高级别的桶保存权值较大的点，相应的权值较小的点都放在低级别的桶内，每次扫描都只针对低级别桶中的点。当然随着点的插入和删除，两个桶内的点是需要动态调整的。在DKA算法中，给每个桶一定的范围以及DKD中使用双桶，在一定程度上都是以空间换时间的做法，需要改进。

图 1 一个桶结构的示例
Fig. 1 An Example of the Bucket Data Structure
3 本文提出的Dijkstra算法实现
3.1 网络拓扑关系的建立
上面介绍的各种图的存储结构考虑了图在理论上的各种特征，如有向、无向、带权、出度、入度等。而GIS中的网络一般为各种道路、管网、管线等，这些网络在具有图理论中的基本特征的同时，更具有自己在实际中的一些特点。首先，在GIS中大多数网络都是有向带权图，如道路有单双向问题，电流、水流都有方向（如果是无向图也可归为有向图的特例），且不同的方向可能有不同的权值。更重要的一点是，根据最短路径算法的特性可以知道，顶点的出度是个重要指标，但是其入度在算法里则不必考虑。综合以上4种存储结构的优缺点， 笔者采用了两个数组来存储网络图，一个用来存储和弧段相关的数据（Net-Arc List），另一个则存储和顶点相关的数据（Net-Node Index）。Net-Arc List用一个数组维护并且以以弧段起点的点号来顺序排列，同一起点的弧段可以任意排序。这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻接多重表的特点，即一条边以两顶点表示。Net-Node Index则相当于一个记录了顶点出度的索引表，通过它可以很容易地得到此顶点的出度以及与它相连的第一条弧段在弧段数组中的位置。此外，属性数据作为GIS不可少的一部分也是必须记录的。这样，计算最佳路径所需的网络信息已经完备了。在顶点已编号的情况下，建立Net-Arc List和Net-Node Index两个表以及对Net-Arc List的排序，其时间复杂度共为O(2n+lgn)，否则为O(m+2n+lgn)。这个结构所需的空间也是必要条件下最小的，记录了m个顶点以及n条边的相关信息，与邻接多重表是相同的。图 2 是采用这个结构的示意图。
3.2 快速搜索技术的实现
无论何种算法，一个基本思想都是将点按权值的大小顺序排列，以节省操作时间。前面已经提到过，这两个算法都是以时间换空间的算法，所以在这里有必要讨论存储空间问题 (这部分空间的大小依赖于点的个数及其出度)。根据图中顶点和边的个数可以求出顶点的平均出度e=m/n（m为边数，n为顶点数），这个数值代表了图的连通程度，一般在GIS的网络图中，e∈〔2,5〕。这样,如果当前永久标记的点为t个，那么，下一步需扫描点的个数就约为t～4t个。如果采用链表结构，按实际应用中的网络规模大小，所需的总存储空间一般不会超过100 K。所以完全没有必要采用以时间换空间的做法，相反以空间换时间的做法是完全可行的。在实现这部分时，笔者采用了一个FIFO队列，相应的操作主要是插入、排序和删除，插入和删除的时间复杂度都是O(1)，所以关键问题在于选择一个合适的排序算法。一般可供选择的排序算法有快速排序、堆排序以及归并排序等，其实现的平均时间都为O(nlgn)。经过比较实验，笔者选择了快速排序法。另外，Visual C++提供的run-time库也提供了现成的快速排序的函数qsort( )可供使用。

图 2 基于最佳路径计算的网络拓扑表示
Fig. 2 The Presentation of the Network Topology
Used for Computing the Shortest Path
按照以上思路，笔者用Visual C++实现了吉奥之星（GeoStar）中的最佳路径模块。以北京的街道为数据（共6 313个结点，9 214条弧段(双向)），在主频为133、硬盘为1 G、内存为32 M的机器上，计算一条贯穿全城、长为155.06 km的线路，约需1 s～2 s。如图 3所示。

图 3 GeoStar中最佳路径实现示意图

ps:图片没有办法贴上去.
你可以参考《算法导论》第二版

㈥ 最短路径算法 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写给我。

㈦ 最短路径算法 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算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，本文主要介绍其中的三种。

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
算法具体的形式包括：

确定起点的最短路径问题：即已知起始结点，求最短路径的问题。

确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。

全局最短路径问题：求图中所有的最短路径。
Floyd

求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题。
Floyd-Warshall算法的时间复杂度为O(N^3)，空间复杂度为O(N^2)。

Floyd-Warshall的原理是动态规划：

设Di,j,k为从i到j的只以(1..k)集合中的节点为中间节点的最短路径的长度。

若最短路径经过点k，则Di,j,k = Di,k,k-1 + Dk,j,k-1；

若最短路径不经过点k，则Di,j,k = Di,j,k-1。

因此，Di,j,k = min(Di,k,k-1 + Dk,j,k-1 , Di,j,k-1)。

在实际算法中，为了节约空间，可以直接在原来空间上进行迭代，这样空间可降至二维。

Floyd-Warshall算法的描述如下：

for k ← 1 to n do

for i ← 1 to n do

for j ← 1 to n do

if (Di,k + Dk,j < Di,j) then

Di,j ← Di,k + Dk,j;

其中Di,j表示由点i到点j的代价，当Di,j为 ∞ 表示两点之间没有任何连接。

Dijkstra

求单源、无负权的最短路。时效性较好，时间复杂度为O（V*V+E）,可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。
源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV）。

当是稀疏图的情况时，此时E=V*V/lgV，所以算法的时间复杂度可为O（V^2） 。可以用优先队列进行优化，优化后时间复杂度变为0（v*lgn）。
Bellman-Ford

求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。

Bellman-Ford算法是求解单源最短路径问题的一种算法。

单源点的最短路径问题是指：给定一个加权有向图G和源点s，对于图G中的任意一点v，求从s到v的最短路径。

与Dijkstra算法不同的是，在Bellman-Ford算法中，边的权值可以为负数。设想从我们可以从图中找到一个环

路（即从v出发，经过若干个点之后又回到v）且这个环路中所有边的权值之和为负。那么通过这个环路，环路中任意两点的最短路径就可以无穷小下去。如果不处理这个负环路，程序就会永远运行下去。 而Bellman-Ford算法具有分辨这种负环路的能力。
SPFA

是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k< 与Bellman-ford算法类似，SPFA算法采用一系列的松弛操作以得到从某一个节点出发到达图中其它所有节点的最短路径。所不同的是，SPFA算法通过维护一个队列，使得一个节点的当前最短路径被更新之后没有必要立刻去更新其他的节点，从而大大减少了重复的操作次数。
SPFA算法可以用于存在负数边权的图，这与dijkstra算法是不同的。

与Dijkstra算法与Bellman-ford算法都不同，SPFA的算法时间效率是不稳定的，即它对于不同的图所需要的时间有很大的差别。
在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度仅为O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为Bellman-ford算法，其时间复杂度为O(VE)。
SPFA算法在负边权图上可以完全取代Bellman-ford算法，另外在稀疏图中也表现良好。但是在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的Dijkstra算法，以及它的使用堆优化的版本。通常的SPFA。