最短路算法详解（Dijkstra/Floyd/SPFA/A*算法）_spfa算法、dijkstra算法、a*算法等等

最短路径

在一个无权的图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。由于从一个顶点到另一个顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短（即经过的边数最少）的那条路径叫作最短路径或者最短距离。

对于带权的图，考虑路径上各边的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或带权路径长度。从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或最短距离。

一、Dijkstra算法

1.定义概览

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

2.算法描述

1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2)算法步骤：

a.初始时，S只包含源点，即S＝{v}，v的距离为0。U包含除v外的其他顶点，即:U={其余顶点}，若v与U中顶点u有边，则<u,v>正常有权值，若u不是v的出边邻接点，则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。

c.以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

3.算法实例：

用Dijkstra算法找出以A为起点的单源最短路径步骤如下

4.局限性：Dijkstra没办法解决负边权的最短路径，如图

运行完该算法后，从顶点1到顶点3的最短路径为1,3，其长度为1，而实际上最短路径为1,2,3，其长度为0.

（因为过程中先选择v3，v3被标记为已知，今后不再更新）

5.算法实现：

普通的邻接表用vis作为上面标记的known，dis记录最短距离（记得初始化为一个很大的数）。

void dijkstra(int s)  
{  
    memset(vis,0,sizeof(vis));         
    int cur=s;                     
    dis[cur]=0;  
    vis[cur]=1;  
    for(int i=0;i<n;i++)  
    {  
        for(int j=0;j<n;j++)                       
            if(!vis[j] && dis[cur] + map[cur][j] < dis[j])   //未被标记且比已知的短，可更新   
                dis[j]=dis[cur] + map[cur][j] ;  
  
        int mini=INF;  
        for(int j=0;j<n;j++)                    
            if(!vis[j] && dis[j] < mini)    //选择下一次到已知顶点最短的点。   
                mini=dis[cur=j];  
        vis[cur]=true;  
    }     
}  

struct point  
{  
    int val,id;  
    point(int id,int val):id(id),val(val){}  
    bool operator <(const point &x)const{  
        return val>x.val;  
    }  
};  
void dijkstra(int s)  
{  
    memset(vis,0,sizeof(vis));  
    for(int i=0;i<n;i++)  
        dis[i]=INF;   
  
    priority_queue<point> q;  
    q.push(point(s,0));  
    dis[s]=0;  
    while(!q.empty())  
    {  
        int cur=q.top().id;  
        q.pop();  
        if(vis[cur]) continue;  
        vis[cur]=true;  
        for(int i=head[cur];i!=-1;i=e[i].next)  
        {  
            int id=e[i].to;  
            if(!vis[id] && dis[cur]+e[i].val < dis[id])  
            {  
                dis[id]=dis[cur]+e[i].val;  
                q.push(point(id,dis[id]));  
            }  
        }         
    }  
}  

二、Floyd算法

1.定义概览

Floyd-Warshall算法（Floyd-Warshall algorithm）是解决任意两点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，

同时也被用于计算有向图的传递闭包。Floyd-Warshall算法的时间复杂度为O(N³)，空间复杂度为O(N²)。

2.算法描述

1)算法思想原理：

     Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话，首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题，

我们需要为这个目标重新做一个诠释（这个诠释正是动态规划最富创造力的精华所在）

      从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。所以，我们假设Dis(i,j)为节点u到节点v的

最短路径的距离，对于每一个节点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，

我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有节点k，Dis(i,j)中记录的便是i到j的最短路径的距离。

2).算法描述：

a.从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。 　　

b.对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。

3.算法实例：

邻接矩阵： 

第一步:以定点0作为松弛的点，考虑a[i][j]表示定点i到顶点j经由顶点0的最短路径长度，经过比较，没有任何路径得到修改，因此有： 
 
第二步：以定点1作为松弛的点，考虑a[i][j]表示定点i到顶点j经由顶点1的最短路径长度，经过比较，顶点0到顶点1由原来的没有路径变为0—1—2的路径，其长度为9；因此有： 
 
第三步：以定点2作为松弛的点，考虑a[i][j]表示定点i到顶点j经由顶点2的最短路径长度，经过比较，顶点1到顶点0由原来的没有路径变为1—2—0的路径，其长度为7； 
顶点3到顶点0由原来的没有路径变为3—2—0的路径，其长度为4 
顶点3到顶点3由原来的没有路径变为3—2—1的路径，其长度为4因此有： 
 
第四步：以定点3作为松弛的点，考虑a[i][j]表示定点i到顶点j经由顶点3的最短路径长度，经过比较，顶点0到顶点2由原来的路径长度为9，路径为 0—1—2，变为0—3—2，其长度为8； 
顶点1到顶点0由原来的路径长度为7，路径为1—2—0，变为1—3—2—0，其长度为6； 
顶点1到顶点2由原来的路径长度为4，路径为1—2 ，变为1—3—2 ，其长度为3； 

4.算法实现：

void floyd()  
{  
    for(int k=0;k<n;k++)  
        for(int i=0;i<n;i++)  
            for(int j=0;j<n;j++)  
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);  
}  

三、SPFA（bellman-ford）

1.原理过程：

2.代码实现：

void SPFA(int s)    
{    
    for(int i=0;i<n;i++)    
        dis[i]=INF;    
    
    bool vis[MAXN]={0};    
        
    vis[s]=true;    
    dis[s]=0;    
        
    queue<int> q;    
    q.push(s);    
    while(!q.empty())    
    {    
        int cur=q.front();    
        q.pop();    
        vis[cur]=false;    
        for(int i=0;i<n;i++)    
        {    
            if(dis[cur] + map[cur][i] < dis[i])    
            {    
                dis[i]=dis[cur] + map[cur][i];    
                if(!vis[i])    
                {    
                    q.push(i);    
                    vis[i]=true;    
                }    
            }               
        }    
    }    
}    

对负圈的判断 code :

bool spfa()      
{      
    for(int i=0;i<=n;i++)      
        dis[i]=INF;      
      
    bool vis[MAXN]={0};      
    int cnt[MAXN]={0};      
    queue<int> q;      
    dis[0]=0;      
    vis[0]=true;      
    cnt[0]=1;      
    q.push(0);      
      
    while(!q.empty())      
    {      
        int cur=q.front();      
        q.pop();      
        vis[cur]=false;      
      
        for(int i=head[cur];i!=-1;i=e[i].next)      
        {      
            int id=e[i].to;      
            if(dis[cur] + e[i].val > dis[id])      
            {      
                dis[id]=dis[cur]+e[i].val;      
                if(!vis[id])      
                {      
                    cnt[id]++;      
                    if(cnt[cur] > n)      
                        return false;      
                    vis[id]=true;      
                    q.push(id);      
                }      
            }      
        }      
    }      
    return true;      
}

3.优化

4.应用：

四 、A*搜索算法