最短路问题

　　单源最短路径

　　Dijkstra算法：

　　基本算法：

　　将图G中所有的顶点V分成两个顶点集合Va和Vb。如果源点S到u的最短路径已经确定，则点u属于集合Va,否则属于集合Vb。最开始的时候Va只包含源点S,其余的点属于Vb，算法结束时所有由源点S可达的点属于Va，其他点仍然留在Vb中。可以在求出最短路径长度的同时记录最短路径，方法是记录终点的前一个点，这样只要倒着查回去就能确定整条最短路径。

　　具体步骤：

　　（1）首先初始化，将源点S到图中各点的直接距离当做初始值记录为S到各点的最短距离，如果不能直接到达，记为INF，S到S的距离为0。

　　（2）在所有属于Vb的点中找一个S到其路径长度最短的点u，将u从Vb中除去，加入到Va中。既当前求出的从S到u的路径为S到u的最短路径。

　　（3）由新确定的u点更新S到Vb中每一点v的距离，如果S到u的距离加上u到v的直接距离小于当前S到v的距离，表明新生成的最短路径的长度比前面计算的更短，那么就更新这个距离，同时更新最短路径。

　　（4）重复步骤（2）、（3）的过程，知道Vb中已经没有或者Vb中的点都不能由源点S到达。

　　其实Dijkstra算法和Prim算法的思想和实现非常相像，只是由于问题不同，实现过程中计算内容不同，前者计算路径长度，后者比较边的长短。

　　实现办法：

　　1.直接实现

　　代码如下：

const int maxn=10001;
void Dijkstra(int n,int dist[maxn],int map[maxn][maxn],int pre[maxn],int s)
{
    int i,j,k;
    int min;
    bool p[maxn];//记录该点属于哪个集合
    for(i=1;i<=n;i++)
    {
        p[i]=false;
        if(i!=s)
        {
            dist[i]=map[s][i];
            pre[i]=s;
        }
    }
    dist[s]=0;
    p[s]=true;
    for(i=1;i<=n-1;i++)//循环n-1次，求S到其他n-1个点的最短距离
    {
        min=INT_MAX;
        k=0;
        for(j=1;j<=n;j++)
        {
            if(!p[j]&&dist[j]<min)
            {
                min=dist[j];
                k=j;
            }
        }
        if(k==0)return;
        p[k]=true;
        for(j=1;j<=n;j++)
        {
            if(!p[j]&&map[k][j]!=INT_MAX&&dist[j]>dist[k]+map[k][j])
            {
                dist[j]=dist[k]+map[k][j];
                pre[j]=k;
            }
        }
    }
}

　　时间复杂度为O(n²)。

　　2.堆实现

　　注意比较可以发现，除了更新dist数组的部分以外，Dijkstra和Prim算法的实现完全相同。

　　代码如下：

//堆
struct HeapElement
{
    int key,value;
};
struct MinHeap
{
    HeapElement H[maxn];
    int size;
    int postion[maxn];
    void init(){H[size=0].value=-INF;}
    void ins(int key,int value)
    void decrease(int key,int value)
    void delmin()
}H;
//边
struct edge 
{
    int to,w,next;
}edge[maxm];
int n,m;
long long dist[maxn];
int head[maxn];
void Dijkstra(int s)
{
    int i,j,k;
    H.init(true);
    for(i=1;i<=n;i++)
    {
        H.ins(i,INF);
        dist[i]=INF;
    }
    dist[s]=0;
    H.decrease(s,0);
    for(i=s;;)
    {
        H.delmin();
        for(k=head[i];k!=-1;k=edge[k].next)
        {
            if(dist[i]<dist[j=edge[k].to]-edge[k].w)
            {
                dist[j]=dist[i]+edge[k].w;
                H.decrease(j,dist[j]);
            }
        }
        if(H.size)i=H.H[1].key;
        else break;
    }
}

　　时间复杂度为O((n+m)logn)，算法主要用于图的边数相对点数的平方很小的时候，能够提高效率。

　　Bellman-Ford算法

　　Dijkstra算法对于带负权边的图无能为力，而Bellman_Ford算法可以解决这个问题。

　　基本算法：

　　Bellman-Ford算法基于动态规划，反复用已有的边来更新最短距离，Bellman-Ford算法的核心思想是松弛。如果dist[u]和dist[v]满足dist[v]≤dist[u]+map[u][v],dist[v]就应该被更新为dist[u]+map[u][v]。反复利用上式对dist数组进行松弛，如果没有负权回路的话，应当会在n-1次松弛之后结束。原因在于考虑对每条边进行一次松弛的时候，得到的实际上是至多经过0个点的最短路径，对每条边进行两次松弛的时候得到的是至多经过1个点的最短路径，如果没有负权回路，那么任意两点间的最短路径至多经过n-2个点，因此经过n-1次松弛操作后应该可以得到最短路径。如果有负权回路，那么第n次松弛操作仍然会成功。

　　代码如下：

bool BellmanFord(int s,int head[maxn],NODE edge[maxm],int dist[maxn])
{
    int i,j,k;
    for(i=0;i<n;i++)dist[i]=inf;
    dist[s]=0;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n;j++)
        {
            if(dist[j]==inf)continue;
            for(k=head[j];k!=-1;k=edge[k].next)
            {
                if(edge[k].w!=inf&&dist[edge[k].to]>dist[j]+edge[k].w)
                {
                    dist[edge[k].to]=dist[j]+edge[k].w
                }
            }
        }
    }
    for(j=0;j<n;j++)
    {
        if(dist[j]==inf)continue;
        for(k=head[j];k!=-1;k=edge[k].next)
        {
            if(edge[k].w!=inf&&dist[edge[k].to]>dist[j]+edge[k].w)
            return false;
        }
    }
    return true;
}

　　Bellman-Ford算法在极限情况下需要进行n-1次更新，每次更新需要遍历每一条边，所以Bellman-Ford算法的时间复杂度为O(n*m)，也就是说他的时间复杂度比Dijkstra算法高。

　　SPFA算法

　　SPFA算法比Bellman-Ford算法的时间复杂度要低。

　　基本算法：

　　设立一个先进先出的队列用来保存待优化的节点，优化时每次取出队首节点u，并且用u点当前的最短路径估计值对离开u点所指向的节点v进行松弛操作，如果v点的最短路径估计值有所调整，且v点不在当前的队列中，就将v点放入队尾。这样不断从队列中取出节点来进行松弛操作，直至队列空为止。这个算法保证只要最短路径存在，SPFA算法必定能求出最小值。

　　SPFA算法同样可以判断负环，如果某个点弹出队列的次数超过n-1次，则存在负环。

　　代码如下：

bool SPFA(int s,int head[maxn],NODE edge[maxm],int dist[maxn])
{
    int i,k;
    int dist[maxn];
    bool vis[maxn];
    int queue[maxn<<2];
    int iq;
    int top;
    int outque[maxn];
    for(i=0;i<=n;i++)
    {
        dist[i]=inf;
    }
    memset(vis,0,sizeof(vis));
    memset(outque,0,sizeof(outque));
    iq=0;
    queue[iq++]=s;
    vis[s]=true;
    dist[s]=0;
    i=0;
    while(i!=iq)
    {
        top=queue[i];
        vis[top]=false;
        outque[top]++;
        if(outque[top]>n)return false;
        k=head[top];
        while(k>=0)
        {
            if(dist[edge[k].b]-edge[k].w>dist[top])
            {
                dist[edge[k].b]=edge[k].w+dist[top];
                if(!vis[edge[k].b])
                {
                    vis[edge[k].b]=true;
                    queue[iq++]=edge[k].b;
                }
            }
            k=edge[k].next;
        }
        i++;
    }
    return true;
}

　　期望的时间复杂度为O(k*e)，其中k为所有顶点进队的平均次数，可以证明一般k≤2。可见SPFA算法非常快，不过其效率不很稳定，对于某些数据可能还不如直接实现的Dijkstra算法。

　　

　　每对顶点间的最短距离

　　下面介绍一种编程简单、时间效率也可以接受的算法--Floyd算法。

　　对图的唯一要求是不能有负环。

　　基本算法：

　　Floyd算法基于动态规划的思想，以u到v的最短路径至少经过前k个点为转移状态进行计算，通过k的增加达到寻找最短路径的目的。当k增加1时，最短路径要么不变，如果改变，必定通过第k个点，也就是说当起点u到第k个点的最短路径加上第k个点到终点v的最短路径小于不经过第k个点的最优最短路径长度的时候，更新u到v的最短路径。当k=n时，u到v的最短路径就确定了。

　　代码如下：

const int maxn=101;
void Floyd(int n,int map[][maxn],int dist[maxn],int pre[][maxn])
{
    int i,j,k;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            dist[i][j]=map[i][j];
            pre[i][j]=i;
        }
    }
    for(k=1;k<=n;k++)
    {
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=n;j++)
            {
                if(dist[i][k]!=INT_MAX&&dist[k][j]!=INT_MAX&&
                   dist[i][k]+dist[k][j]<dist[i][j])
                   {
                       dist[i][j]=dist[i][k]+dist[k][j];
                       pre[i][j]=pre[k][j];
                   }
            }
        }
    }
}

　　时间复杂度：O(n³)。

参考文献：《图论及应用》哈尔滨工业大学出版社

特此申明：严禁转载

2014-02-20