单源最短路径问题的有效算法

㈠ vc环境 最短路径算法

单源最短路径算法---Dijkstra算法
转自:http://space.flash8.net/space/html/07/14107_itemid_400760.html

算法介绍
Dijkstra算法是由荷兰计算机科学家艾兹格·迪科斯彻发现的。算法解决的是有向图中最短路径问题。

举例来说，如果图中的顶点表示城市，而边上的权重表示着城市间开车行经的距离。 Dijkstra算法可以用来找到两个城市之间的最短路径。

Dijkstra 算法的输入包含了一个有权重的有向图G，以及G中的一个来源顶点S。我们以V表示G中所有顶点的集合。每一个图中的边，都是两个顶点所形成的有序元素对。 (u,v)表示从顶点u到v有路径相连。我们以E所有边的集合，而边的权重则由权重函数w: E → [0, ∞]定义。因此，w(u,v)就是从顶点u到顶点v的非负花费值(cost)。边的花费可以想象成两个顶点之间的距离。任两点间路径的花费值，就是该路径 上所有边的花费值总和。已知有V中有顶点s及t，Dijkstra算法可以找到s到t的最低花费路径(i.e. 最短路径)。这个算法也可以在一个图中，找到从一个顶点s到任何其他顶点的最短路径。

算法描述
这个算法是通过为每个顶点v保留目前为止所找到的从s到v的最短路径来工作的。 初始时，源点s的路径长度值被赋为0（d[s]=0），同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于V中所有 顶点v除s外d[v]= ∞）。当算法结束时，d[v]中储存的便是从s到v的最短路径，或者如果路径不存在的话是无穷大。 Dijstra算法的基础操作是边的拓展：如果存在一条从u到v的边，那么从s到u的最短路径可以通过将边(u,v)添加到尾部来拓展一条从s到v的路 径。这条路径的长度是d[u]+w(u,v)。如果这个值比目前已知的d[v]的值要小，我们可以用新值来替代当前d[v]中的值。拓展边的操作一直执行 到所有的d[v]都代表从s到v最短路径的花费。这个算法经过组织因而当d[u]达到它最终的值的时候没条边(u,v)都只被拓展一次。

算法维护两个顶点集S和Q。集合S保留了我们已知的所有d[v]的值已经是最短路径的值顶点，而集合Q则保留其他所有顶点。集合S初始状态为空，而后每一步 都有一个顶点从Q移动到S。这个被选择的顶点是Q中拥有最小的d[u]值的顶点。当一个顶点u从Q中转移到了S中，算法对每条外接边(u,v)进行拓展。

伪码
在下面的算法中,u:=Extract_Min(Q)在在顶点集Q中搜索有最小的d[u]值的顶点u。这个顶点被从集合Q中删除并返回给用户。

function Dijkstra(G, w, s)

// 初始化
for each vertex v in V[G] {
d[v] := infinity
previous[v] := undefined
d[s] := 0
}

S := empty set
Q := set of all vertices

while Q is not an empty set { // Dijstra算法主体
u := Extract_Min(Q)
S := S union {u}
for each edge (u,v) outgoing from u
if d[v] > d[u] + w(u,v) // 拓展边(u,v)
d[v] := d[u] + w(u,v)
previous[v] := u
}

如果我们只对在s和t之间寻找一条最短路径的话，我们可以在第9行添加条件如果满足u=t的话终止程序。

现在我们可以通过迭代来回溯出s到t的最短路径

1 S := empty sequence
2 u := t
3 while defined u
4 insert u to the beginning of S
5 u := previous[u]

现在序列S就是从s到t的最短路径的顶点集.

时间复杂度
我们可以用大O符号将Dijkstra算法的运行时间表示为边数m和顶点数n的函数。

Dijkstra算法最简单的实现方法是用一个链表或者数组来存储所有顶点的集合Q,所以搜索Q中最小元素的运算(Extract-Min(Q))只需要线性搜索Q中的所有元素。这样的话算法的运行时间是O(n2)。

对 于边数少于n2稀疏图来说，我们可以用邻接表来更有效的实现Dijkstra算法。同时需要将一个二叉堆或者斐波纳契堆用作优先队列来寻找最小的顶点 (Extract-Min)。当用到二叉堆的时候，算法所需的时间为O((m+n)log n)，斐波纳契堆能稍微提高一些性能，让算法运行时间达到O(m + n log n)。

相关问题和算法
在Dijkstra 算法的基础上作一些改动，可以扩展其功能。例如，有时希望在求得最短路径的基础上再列出一些次短的路径。为此，可先在原图上计算出最短路径，然后从图中删 去该路径中的某一条边，在余下的子图中重新计算最短路径。对于原最短路径中的每一条边，均可求得一条删去该边后子图的最短路径，这些路径经排序后即为原图 的一系列次短路径。

OSPF（open shortest path first, 开放最短路径优先）算法是Dijkstra算法在网络路由中的一个具体实现。

与Dijkstra算法不同，Bellman-Ford算法可用于具有负花费边的图，只要图中不存在总花费为负值且从源点 s 可达的环路（如果有这样的环路，则最短路径不存在，因为沿环路循环多次即可无限制的降低总花费）。

与最短路径问题有关的一个问题是旅行商问题(traveling salesman problem)，它要求找出通过所有顶点恰好一次且最终回到源点的最短路径。该问题是NP难的；换言之，与最短路径问题不同，旅行商问题不太可能具有多项式时间算法。

如果有已知信息可用来估计某一点到目标点的距离，则可改用A*算法 ，以减小最短路径的搜索范围。

另外，用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：
Dijkstra算法
A*算法
SPFA算法
Bellman-Ford算法
Floyd-Warshall算法
Johnson算法
所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。

㈡ 谁能介绍下 n-最短路径 的算法

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

确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题。
确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径。
全局最短路径问题 - 求图中所有的最短路径。
用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：

Dijkstra算法
A*算法
Bellman-Ford算法
Floyd-Warshall算法
Johnson算法

所谓单源最短路径问题是指：已知图G＝（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。

首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。

㈢ 求单源最短路径算法和程序（程序不要用数据结构的）

你想输出路径吗？
记录一下每个点的直接前驱，然后反向查找
#include <stdio.h>

const int maxdot=100;
int dist[maxdot];
int previous[maxdot]; //record the directly previous node

void ShortPaths(int v,int c[maxdot][maxdot],int n)
{
int i,j; bool s[maxdot];
int p[maxdot][maxdot];
for(i=1;i<=n;i++)
{
dist[i]=c[v][i];
previous[i]=v;
s[i]=false;
}
dist[v]=0;s[v]=true;
for(i=1;i<n;i++)
{
int temp=10000;
int u=v;
for(j=1;j<=n;j++)
{
if(!s[j]&&(dist[j]<temp))
{
u=j;
temp=dist[j];
}
}
s[u]=true;
for(j=1;j<=n;j++)
{
if(!s[j]&&(c[u][j]<1000))
{
int newdist=dist[u]+c[u][j];
if(newdist<dist[j])
{
dist[j]=newdist;
previous[j]=u; //update the directly previous node
}
}
}
}
}

void find(int v,int u) // 'v' here must be identical with the 'v' in above function
{
//output the path in reverse order
while(u!=previous[u])
{
u=previous[u]; // retrieve the previous node
printf("%d\n",u);
}
}

㈣ 如何证明求最短路劲的Dijkstra算法的正确性

Dijkstra算法（单源最短路径）

单源最短路径问题，即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前，必须弄清楚最短路径的最优子结构性质。

一.最短路径的最优子结构性质

该性质描述为：如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，k和s是这条路径上的一个中间顶点，那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。

假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径，则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离，那么必定存在另一条从k到s的最短路径P'(k,s)，那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。

二.Dijkstra算法

由上述性质可知，如果存在一条从i到j的最短路径(Vi.....Vk,Vj)，Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径，Dijkstra就提出了以最短路径长度递增，逐次生成最短路径的算法。譬如对于源顶点V0，首先选择其直接相邻的顶点中长度最短的顶点Vi，那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路，

假设存在G=<V,E>，源顶点为V0，U={V0},dist[i]记录V0到i的最短距离，path[i]记录从V0到i路径上的i前面的一个顶点。

1.从V-U中选择使dist[i]值最小的顶点i，将i加入到U中；

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]})

3.知道U=V，停止。

㈤ 最短路径的解决方法

用于解决最短路径问题的算法被称做“最短路径算法”， 有时被简称作“路径算法”。 最常用的路径算法有：
Dijkstra算法
SPFA算法Bellman-Ford算法
Floyd算法Floyd-Warshall算法
Johnson算法
A*算法
所谓单源最短路径问题是指：已知图G=（V，E），我们希望找出从某给定的源结点S∈V到V中的每个结点的最短路径。
首先，我们可以发现有这样一个事实：如果P是G中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。

㈥ 最短路问题的单源最短路径

包括确定起点的最短路径问题，确定终点的最短路径问题（与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。） 。求解单源最短路径问题可以采用Dijkstra算法，时间复杂度为O(|V|^2)。Dijkstra算法可以使用斐波那契堆、配对堆等支持Decrease-Key操作的数据结构来进一步优化，优化后的时间复杂度为O(|E|+|V|log|V|)。

㈦ 单源最短路径的Dijkstra算法

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。
2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。
3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。
4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。 SPFA实际上是Bellman-Ford基础上的队列优化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每条边(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
boolSPFA(intsource)
{
deque<int>dq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成
while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++)
{
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}

㈧ 计算机网络的最短路径算法有哪些对应哪些协议

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法有：
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。

㈨ 数学最短路径问题最方便的解法是什么

用于解决最短路径问题的算法被称做“最短路径算法” ，有时被简称作“路径算法” 。最常用 的路径算法有： 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 算法的描述如下： 1.for k ← 1 to n do 2.for i ← 1 to n do 3.for j ← 1 to n do 4.if (Di,k + Dk,j<Di,j) then 5.Di,j ← Di,k + Dk,j; 其中 Di,j 表示由点 i 到点 j 的代价，当 Di,j 为∞表示两点之间没有任何连接。 Dijkstra 求单源、无负权的最短路。时效性较好，时间复杂度为 O（V*V+E） 。 源点可达的话，O（V*lgV+E*lgV）=>O（E*lgV） 。 当是稀疏图的情况时，此时 E=V*V/lgV，所以算法的时间复杂度可为 O（V^2） 。若是斐波那 契堆作优先队列的话，算法时间复杂度，则为 O（V*lgV + E） 。 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<<V） 。 。 与 Bellman-ford 算法类似， SPFA 算法采用一系列的松弛操作以得到从某一个节点出发到达图 中其它所有节点的最短路径。所不同的是，SPFA 算法通过维护一个队列，使得一个节点的 当前最短路径被更新之后没有必要立刻去更新其他的节点， 从而大大减少了重复的操作次数。 SPFA 算法可以用于存在负数边权的图，这与 dijkstra 算法是不同的。 与 Dijkstra 算法与 Bellman-ford 算法都不同，SPFA 的算法时间效率是不稳定的，即它对于不 同的图所需要的时间有很大的差别。 在最好情形下，每一个节点都只入队一次，则算法实际上变为广度优先遍历，其时间复杂度 仅为 O(E)。另一方面，存在这样的例子，使得每一个节点都被入队(V-1)次，此时算法退化为 Bellman-ford 算法，其时间复杂度为 O(VE)。 SPFA 算法在负边权图上可以完全取代 Bellman-ford 算法， 另外在稀疏图中也表现良好。 但是 在非负边权图中，为了避免最坏情况的出现，通常使用效率更加稳定的 Dijkstra 算法，以及 它的使用堆优化的版本。通常的 SPFA 算法在一类网格图中的表现不尽如人意。 

㈩ ArcGIS Engine10.2中的最短路径算法是什么算法有相关C#代码吗

最短路径算法——Dijkstra算法，又称为单源最短路径，所谓单源是在一个有向图中，从一个顶点出发，求该顶点至所有可到达顶点的最短路径问题。要顺利实现算法，要求理解Dijstra的算法，同时还要理解图的一些基本概念，图由节点和边构成，将节点和边看成对象，每个对象有自己的特有属性，如在GIS中，一个节点必须都有ID，横坐标，纵坐标等基本属性，边有起点节点，终点节点，长度等属性，而最短路径分析，就是根据边的长度(权值)进行分析的。