最短路径问题(图的WPL)

最短路径问题的抽象

  • 在网络中，求两个不同顶点之间所有路径中，边的权值之和最小的那一条路径
    • 这条路径就是两点之间的最短路径(Shortest Path)
    • 第一个顶点为源点(Source)
    • 最后一个顶点为终点(Destination)

问题分类

  • 单源点最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
    • (有向)无权图
    • (有向)有权图
    • 无向图是一种特殊的有向图，与有向图的原理相同
  • 多源点最短路径问题：求任意两顶点间的最短路径
    • 从某任意源点出发，求所有源点所有其他顶点的最短路径

无权图的单源点最短路径算法

  • 按照递增(非递减)的顺序找出各个顶点的最短路径
    • 这种情况的最短路径的本质：顶点与源点之间的顶点最少
      • 间隔的顶点最少——高度/深度/层数最少
      • 由BFS逐层搜索找到符合条件的最短路径
void BFS(Vertex S)
{
    Enqueue(S,Q);
    while(!Isempty(Q))
    {
        V=Dequeue(Q);
        for(V的每个邻接点W)
            if(!visited[W])
            {
                visited[W]=true;
                Enqueue(W,Q);
            }
    }
}

无权图的单源点最短路径BFS算法伪代码描述：

void UnweightedMinPath(Vertex S)
{
    Enqueue(S,Q);
    while(!Isempty(Q))
    {
        V=Dequeue(Q);
        for(V的每个邻接点W)
            if(dist[W]==-1) //这种情况dist数组初始化为正无穷、负无穷、-1等都可以，只要是权值不可能取到的值即可
            {               //注意不能初始化为0，因为dist[S]=0
                dist[W]=dist[V]+1;      //V的每个邻接点V的距离是1，与源点的距离是dist[V]+1
                path[W]=V;
                Enqueue(W,Q);
            }
    }
}
  • dist[W]=S到W的最短距离
  • dist[S]=0
    • 源点S与自身的距离被初始化为0，与其他顶点的距离初始化为-1
  • path[W]=S到W的路上经过的某顶点(W前面经过那一个顶点)
  • 输出S到W的路径上顶点的方法：借助堆栈，从路径末端顶点开始开始向前搜索path[i]，直到源点S，然后将顶点全部弹出
  • BFS时间复杂度T=O(v+e)T=O(v+e)

有权图的单源点最短路径算法

  • 按照递增的顺序找出各个顶点的最短路径
    • 仍然按照BFS的方式——每层寻找最短路径时要考虑权值——Dijkstra算法(BFS的扩展、贪心策略)

Dijkstra算法

  • 令S={源点s+已经确定了最短路径的顶点viv_i}
  • 对任一未收录的顶点v，定义dist[v]为s到v的最短路径长度，但该路径仅经过s中的顶点
    • 即路径s−(vi∈S)−vs-(v_i ∈ S)-v的最小长度
  • 路径仅经过s中的顶点：若路径是按照递增(非递减)的顺序生成的，则
    • 真正的最短路径必须只经过S中的顶点
    • 该问题存在最优子结构特征
      • 假设从源点到终点的最短路径中去掉终点，那么倒数第二个顶点到源点之间仍然应该是这两点之间的最短路径
        • 因为最后两点之间的距离已确定，所以终点的最短路径需要此路径上倒数第二个顶点也满足其最短路径
        • 依此类推，最短路径中的每个点都应该是另一条最短路径上的顶点
        • 并且由于收录顶点是按距离递增的顺序，所以如果顶点v的最短路径中包含未收录的顶点，则一定不是按照距离递增顺序收录的
      • Dijkstra算法不能解决有负边的情况，因为如果存在负边则意味着两点之间再加上一条边后路径可以变小
        • 此时去掉一条负边后剩下的路径不一定最短，不满足最优子结构
        • 某些情况下可能存在负值圈negative-cost-cycle，即在一个回路中走一圈后反而距离和为负，此时最短距离为负无穷
  • 每次从未收录的顶点中选一个dist最小的收录(贪心算法)
  • 增加一个v进入S，可能影响另外一个w的dist值
    • 如果新增收录v后导致w的dist值变短
      • v一定在w的最短路径上
      • v和w之间必定存在一条直接相连的边
        • 因为w只经过已经收录过的顶点，如果v和w不存在边的话则说明v和w之间存在其他顶点且未被收录(因为其dist值比v的长))
        • *实际上，收录v只能影响到其邻接点的dist值
  • dist[w]=mindist[w]=min{dist[w],dist[v]+<v,w>dist[w],dist[v]+<v,w>的权重}

Dijkstra算法伪代码描述：

void Dijkstra(Vertex S)
{
    while(1)
    {
        V=未收录顶点中dist最小者;                  //有权图这种情况dist应该初始化为INFINITY
        if(这样的V不存在)break;
        collected[V]=true;
        for(V的每个邻接点W)
            if(collected[W]==false)
                if(dist[V]+E<V,W> < dist[W])
                {                               //存在这种情况：源点到W的路径过长，使源点到V再到W的路径相对更短
                    dist[W]=dist[V]+E<V,W>;
                    path[W]=V;
                }
    }
}

Dijkstra算法的时间复杂度取决于对dist的处理方法
算法1：直接扫描所有未收录顶点——O(v)O(v)

  • 查找dist最小值(v次)——O(v2)O(v^2)
  • 遍历所有邻接点——O(e)O(e)
  • T=O(v2+e)T=O(v^2+e) ——对稠密图效果好

算法2：将dist存在最小堆中

  • 查找dist最小值(v次)——O(vlgv)O(vlgv)
  • 遍历所有邻接点，同时要把新的dist插入堆——O(elge)O(elge)
  • T=O(vlgv+elge)T=O(vlgv+elge) ——对稀疏图效果好

多源点最短路径算法

算法1：直接将Dijkstra算法调用v遍

  • T=O(v3+ev)T=O(v^3+ev) ——对稀疏图效果好(整体上可视作O(v3)O(v^3))

算法2：Floyd算法

  • T=O(v3)T=O(v^3) ——对稠密图效果好

Floyd算法

  • D(k)[i][j]=路径{$i\rightarrow {l\leq k}\rightarrow j$}的最小长度
  • D−1→D0→D1→,...,→Dv−1[i][j]D_{-1}\rightarrow D_0\rightarrow D_1\rightarrow ,..., \rightarrow D_{v-1}[i][j]最后给出了i到j的真正最短距离
    • D(-1)是什么？
      • 直接以图的邻接矩阵形式进行初始化即可(对角元为0，没有边的元素为正无穷)
  • 当D(k-1)已经完成，递推到D(k)时：
    • 或者k∉k ∉ 最短路径{$i\rightarrow {l\leq k}\rightarrow j}，则D_k=D_{k-1}$
    • 或者k∈k ∈ 最短路径{$i\rightarrow {l\leq k}\rightarrow j$}，则该路径必定由两段最短路径组成
      • D(k)[i][j]=D(k-1)[i][k]+D(k-1)[k][j]
  • Floyd算法的核心为：
    • 对于从顶点i到顶点j的最短路径，拿出网中所有的顶点进行如下判断：
      • 如果i到k的路径长度加k到j的路径长度小于i到j的路径长度，则说明存在一条更短的路径，此时更新路径即可
      • 任意的两个顶点全部做以上的判断，最终遍历完成后记录的最终的权值即为对应顶点之间的最短路径
void Floyd(){
    for(i=0;i<N;i++)
        for(j=0;j<N;j++)
        {
            D[i][j]=G[i][j];
            path[i][j]=-1;
        }
    for(k=0;k<N;k++)
        for(i=0;i<N;i++)
            for(j=0;j<N;j++)
                if(D[i][k]+D[k][j]<D[i][j])
                {
                    D[i][j]=D[i][k]+D[k][j];
                    path[i][j]=k;
                }
}

最短路径算法演示

// 浙江大学mooc数据结构
#define MaxVertexNum 100
#define INFINITY 65535
#define ERROR -1
typedef struct AdjVNode *PtrToAdjVNode; 
typedef struct MGNode *PtrToMGNode;
typedef struct LGNode *PtrToLGNode;
typedef struct QNode *Queue;
typedef int ElementType;
typedef int Vertex;
typedef int WeightType;
typedef char DataType;
typedef PtrToLGNode LGraph;
typedef PtrToMGNode MGraph;
struct AdjVNode{
    Vertex AdjV;       
    WeightType Weight; 
    PtrToAdjVNode Next;   
};
typedef struct Vnode{
    PtrToAdjVNode FirstEdge;
    DataType Data;        
} AdjList[MaxVertexNum];
struct MGNode{
    int Nv; 
    int Ne;  
    WeightType G[MaxVertexNum][MaxVertexNum]; 
    DataType Data[MaxVertexNum];     
};
struct LGNode{  
    int Nv;     
    int Ne;     
    AdjList G; 
};
Queue CreateQueue( int );
void AddQ(Queue, ElementType);
bool IsEmpty(Queue);
ElementType DeleteQ(Queue);
/* 邻接表存储 - 无权图的单源最短路算法 */

/* dist[]和path[]全部初始化为-1 */
void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S )
{
    Queue Q;
    Vertex V;
    PtrToAdjVNode W;
    
    Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */
    dist[S] = 0; /* 初始化源点 */
    AddQ (Q, S);

    while( !IsEmpty(Q) ){
        V = DeleteQ(Q);
        for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */
            if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */
                dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */
                path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */
                AddQ(Q, W->AdjV);
            }
    } /* while结束*/
}

/* 邻接矩阵存储 - 有权图的单源最短路算法 */

Vertex FindMinDist( MGraph Graph, int dist[], int collected[] )
{ /* 返回未被收录顶点中dist最小者 */
    Vertex MinV, V;
    int MinDist = INFINITY;

    for (V=0; V<Graph->Nv; V++) {
        if ( collected[V]==false && dist[V]<MinDist) {
            /* 若V未被收录，且dist[V]更小 */
            MinDist = dist[V]; /* 更新最小距离 */
            MinV = V; /* 更新对应顶点 */
        }
    }
    if (MinDist < INFINITY) /* 若找到最小dist */
        return MinV; /* 返回对应的顶点下标 */
    else return ERROR;  /* 若这样的顶点不存在，返回错误标记 */
}

bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S )
{
    int collected[MaxVertexNum];
    Vertex V, W;

    /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */
    for ( V=0; V<Graph->Nv; V++ ) {
        dist[V] = Graph->G[S][V];
        if ( dist[V]<INFINITY )
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    /* 先将起点收入集合 */
    dist[S] = 0;
    collected[S] = true;

    while (1) {
        /* V = 未被收录顶点中dist最小者 */
        V = FindMinDist( Graph, dist, collected );
        if ( V==ERROR ) /* 若这样的V不存在 */
            break;      /* 算法结束 */
        collected[V] = true;  /* 收录V */
        for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */
            /* 若W是V的邻接点并且未被收录 */
            if ( collected[W]==false && Graph->G[V][W]<INFINITY ) {
                if ( Graph->G[V][W]<0 ) /* 若有负边 */
                    return false; /* 不能正确解决，返回错误标记 */
                /* 若收录V使得dist[W]变小 */
                if ( dist[V]+Graph->G[V][W] < dist[W] ) {/* 因为初始化为INFINITY，所以此句包含源点和第一个顶点的情况 */
                    dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */
                    path[W] = V; /* 更新S到W的路径 */
                }
            }
    } /* while结束*/
    return true; /* 算法执行完毕，返回正确标记 */
}

/* 邻接矩阵存储 - 多源最短路算法 */

bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] )
{
    Vertex i, j, k;

    /* 初始化 */
    for ( i=0; i<Graph->Nv; i++ )
        for( j=0; j<Graph->Nv; j++ ) {
            D[i][j] = Graph->G[i][j];  /* D[i][j]初始化为i,j之间的直接路径长度 */
            path[i][j] = -1;
        }

    for( k=0; k<Graph->Nv; k++ )
        for( i=0; i<Graph->Nv; i++ )
            for( j=0; j<Graph->Nv; j++ )
                if( D[i][k] + D[k][j] < D[i][j] ) {
                    D[i][j] = D[i][k] + D[k][j];
                    if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */
                        return false; /* 不能正确解决，返回错误标记 */
                    path[i][j] = k;
                }
    return true; /* 算法执行完毕，返回正确标记 */
}