最短路径

来自NOCOW

跳转到：导航, 搜索

[编辑] 介绍

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

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

用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。

注：以下的Dijkstra和Bellman-Ford算法中都使用了松弛操作。

[编辑] 常用算法简介

最常用的路径算法有：

[编辑] Dijkstra算法

详细介绍
Dijkstra复杂度是O(N^2)，如果用binary heap优化可以达到O((E+N)logN)，用fibonacci heap可以优化到O(NlogN+E)
其基本思想是采用贪心法，对于每个节点v[i]，维护估计最短路长度最大值，每次取出一个使得该估计值最小的t，并采用与t相连的边对其余点的估计值进行更新，更新后不再考虑t。
在此过程中，估计值单调递减，所以可以得到确切的最短路。

Dijkstra 程序：

//函数返回从节点s到节点e的最短路，共n个节点
long dijk(long s,long e)
{
     const long infi=999999999;
 
     long dis[n]={0};
     bool used[n]={false};
     long min,next;
     memset(dis,255,sizeof(dis));
     dis[s]=0;
 
     for(long i=1;i<=n;i++)
        {
         min=infi;
         for(long j=1;j<=n;j++)
            if(!used[j] && dis[j]!=-1 && dis[j]<min)
              {
               min=dis[j];
               next=j;
              }
         if(min!=infi)
           {
            used[next]=true;
            for(long j=1;j<=n;j++)
               if(!used[j] && map[next][j]!=-1 && (dis[j]>map[next][j]+dis[next] || dis[j]==-1))
                 dis[j]=map[next][j]+dis[next];
           }
        }
 
     return dis[e];
}
//By Stanso

void Dijkstra(){
     for(int i=1;i<=n;i++)
      dis[i] = map[1][i];
 
     int k;
     for(int i=1;i<n;i++){
      int tmin = maxint;
      for(int j=1;j<=n;j++)
       if( !used[j] && tmin > dis[j] ){
        tmin = dis[j];
        k = j;    
       } 
      used[k] = 1;
      for(int j=1;j<=n;j++)
       if( dis[k] + map[k][j] < dis[j] ) 
        dis[j] = dis[k] + map[k][j];
     }
     printf("%d",dis[n]);
}
 
/* 求1到N的最短路,dis[i] 表示第i个点到第一个点的最短路 By Ping*/

[编辑] Floyd-Warshall算法

详细介绍
Floyd是计算每对点间最短路径（APSP)的经典算法。
时间复杂度是雷打不动的O(n^3)

C++ Code

for(int k=1;k<=n;k++)
 for(int i=1;i<=n;i++)
  for(int j=1;j<=n;j++){
   if( map[i][k] != maxint && map[k][j] != maxint )
    if( map[i][k] + map[k][j] < map[i][j] )
     map[i][j] = map[i][k] + map[k][j];
  }
 
/* maxint 为极大值 表示不连通  By Ping ^.^ */

Pascal Code

for i:=1 to n do
  for j:=1 to n do
    for k:=1 to n do
      if (i<>j) and (j<>k) and (i<>k) and (f[j,i]+f[i,k]<f[j,k]) then
        f[j,k]:=f[j,i]+f[i,k];
//初始值为maxlongint 表示不连通  By Fkc

[编辑] Bellman-Ford算法

详细介绍
Bellman-Ford主要是用于负权图。Bellman-Ford算法即标号修正算法。
实践中常用到的方法通常是FIFO标号修正算法和一般标号修正算法的Dequeue实现。
前者最坏时间复杂度是O(nm), 是解决任意边权的单源最短路经问题的最优强多项式算法。
也可以用这个算法判断是否存在负权回路.

SPFA算法

SPFA就是bellmanford的一种实现方式。
SPFA算法就是上面说的FIFO标号修正算法, 请参见《网络流：理论、算法与应用》。

SPFA程序：

//SPFA(邻接矩阵) 详细注释
#include <iostream>
#define INFINITY 999999999
using namespace std;
long map[3000][3000]={0};//map[i][j]邻接矩阵
long queue[30000]={0};//queue[i]队列
long link[3000][3000]={0};//link[i][0] i点的出度  link[i][j] i点的第j条边指向
long dist[3000]={0};//dist[i] i点到起点距离
bool used[3000]={0};//used[i] i点是否在队列中
long node,edge,start,end;
void spfa(long s)//s为当前起点
{
     long left,right,now,nxt;//now是当前队列头结点 
     for(long i=0;i<=node;i++)
        dist[i]=INFINITY;
     dist[s]=0;//将起点到起点距离设为0 
     left=right=1;
     queue[left]=s;//将起点入队 
     used[s]=true;
     while(left<=right)
          {
           now=queue[left];
           for(long i=1;i<=link[now][0];i++)
           {
            nxt=link[now][i];//nxt为下一个节点 
            if(dist[nxt]>dist[now]+map[now][nxt])//如果起始点到当前节点的第i个指向结点的距离>起始点到当前节点的距离+当前节点到当前节点到当前节点的第i个指向结点的距离 
              {
               dist[nxt]=dist[now]+map[now][nxt];//更新始点到当前节点的第i个指向结点的距离
               if(!used[nxt])//若当前节点的第i个指向结点不在队列中，就将其加入队列 
               {queue[++right]=nxt; used[nxt]=true;}
              }
           }
           used[left++]=false;//将当前节点出队 
          }
     return;
}
int main()
{
    cin >>node>>edge>>start>>end;
    long node1,node2,val;
    for(long i=1;i<=edge;i++)//邻接矩阵无向图读入 
       {
        cin>>node1>>node2>>val;
        map[node1][node2]=map[node2][node1]=val;
        link[node1][0]++;
        link[node1][link[node1][0]]=node2;
        link[node2][0]++;
        link[node2][link[node2][0]]=node1;
       }
    spfa(start);
    cout <<dist[end];//输出起始点到终点的最短距离
    system("pause");
}
//By Stanso

void spfa()
{
     int t,p;
     queue[cl] = 1;
     while( cl < op ){
      int p = queue[cl++];
      for(t=head[p][0]; t!=0; t=list[t].next ){
       if( way[p] != maxint && way[p] + list[t].w < way[list[t].r] ){
        way[list[t].r] = way[p] + list[t].w;
        queue[op++] = list[t].r;
       }
      }
     }
     printf("%d",way[n]);
}
 
 
/* queue为优先队列,链表存图(list) by Ping ^.^ */
/* 用这种方法存在队列里面很浪费空间，如果spfa退化到Bellman-Ford的复杂度之后，但是我们发现，在队列中的有效元素不可能多于图的节点总数，所以，我们可以用循环
队列来存图，具体方法自己琢磨一下。大致是把移动首尾指针的 l++,r++替换成 l=(l+1)%(n+1)  队列的状态改为l!=r*/