关于「最短路径问题」的一些理解

Feb. 8th, 2016


算法 最短路径问题


最近看了最短路问题,记录一下,基本都是从书上直接抄下来的,没什么思想,希望以后温故的时候可以知点新吧。

最短路径问题分为两类,一类是从单个顶点出发到达其余所有顶点的最短路径问题;一类是所有顶点对间的最短路径问题。

单源最短路径问题

松弛技术是各种最短路径算法的基础,通过对边设置属性$d[v]$,用来描述从源点$s$到$v$的最短路径上权值的上界,即最短路径估计。对边$(u,v)\in E$执行

$if(d[v]>d[u]+w(u,v))
d[v]=d[u]+w(u,v)$

这样的操作,在通过逻辑关系保证足够多次松弛操作的条件下,使得最短路径问题得以解决。主要有Bellman_ford算法和Dijkstra算法两种思想。

Bellman-Ford算法

对于一个顶点数为$V$,边数为$E$的无负权回路图,由于从任意一点$s$到其他所有定点的最短路径最长为$V-1$(这里最短路径均为简单路径,所有权为0的回路均从路径中移除,路径长度不变),因此对所有边都进行至多$V-1$次松弛操作,一定可以得到从$s$出发到其他顶点的最短路径;对所有边进行第$n$次松弛操作后,一定可以得到由$s$出发的长度为$n$的最短路径,以此类推。

时间复杂度为$O(VE)$,对于稠密图(即$E=O(V^{2})$),复杂度为$O(V^{3})$;对于稀疏图(即$E=O(V)$),复杂度为$O(V^{2})$,效率较低

若从$s$出发到某点$v$的路径中存在负环,由于绕负环回路路径长度可以达到$-\infty$,因此进行至多$V-1$次松弛之后,得到的路径长度并非最小,此时对每一条边进行检验,若有$d[v]>d[u]+\delta(u,v)$,则说明含有负环回路

/*
*单源最短路bellman_ford算法,复杂度O(VE)
*可以处理负边权图。
*可以判断是否存在负环回路。返回true,当且仅当图中不包含从源点可达的负权回路
*vector<Edge>E;先E.clear()初始化,然后加入所有边
*点的编号从1开始(从0开始简单修改就可以了)
*/
const int INF=0x3f3f3f3f;
const int MAXN=550;
int dist[MAXN];
struct Edge {
    int u,v;
    int cost;
    Edge(int _u=0,int _v=0,int _cost=0):u(_u),v(_v),cost(_cost){}
};
vector<Edge>E;
bool bellman_ford(int start,int n)//点的编号从1开始
{
    for(int i=1;i<=n;i++)dist[i]=INF;
    dist[start]=0;
    for(int i=1;i<n;i++)//最多做n-1次
    {
        bool flag=false;
        for(int j=0;j<E.size();j++)
        {
            int u=E[j].u;
            int v=E[j].v;
            int cost=E[j].cost;
            if(dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                flag=true;
            }
        }
        if(!flag)return true;//没有负环回路,此处优化了一些,如果在松弛过程中已经没有边需要变化,则退出循环,结束算法
    }
    for(int j=0;j<E.size();j++)
        if(dist[E[j].v]>dist[E[j].u]+E[j].cost)
            return false;//有负环回路
    return true;//没有负环回路
}

View Code in Github Repository

SPFA算法

SPFA算法是Bellman-Ford算法的优化,通过队列或者栈进行维护,减少Bellman-Ford算法为了保证正确性而进行的$V\centerdot E$次的松弛操作,但是其最坏算法复杂度仍然是$O(VE)$,实际应用中的平均时间复杂度为$O(kE)$,一般情况下$k\le 2$

/*
*单源最短路SPFA
*时间复杂度 0(kE)
*这个是队列实现,有时候改成栈实现会更加快,很容易修改
*这个复杂度是不定的
*/
const int MAXN=1010;
const int INF=0x3f3f3f3f;
struct Edge
{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA(int start,int n)
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    vis[start]=true;
    dist[start]=0;
    queue<int>que;
    while(!que.empty())que.pop();
    que.push(start);
    memset(cnt,0,sizeof(cnt));
    cnt[start]=1;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v])
                {
                    vis[v]=true;
                    que.push(v);
                    if(++cnt[v]>n)return false;
                    //cnt[i]为入队列次数,用来判定是否存在负环回路
                }
            }
        }
    }
    return true;
}

View Code in Github Repository
View Code in Github Repository

对于有向无回路图的优化

对于没有回路的有向图,可以先通过拓扑排序的方式确定节点之间的线性次序,之后按照拓扑排序的顺序对节点进行一遍松弛处理即可 拓扑排序的时间复杂度为$O(V+E)$,之后松弛操作恰好对每条边都执行了一次,复杂度为$O(E)$,如果用邻接表的形式存储图,则花费的时间为线性级$O(V+E)$

DAG-SHORTEST-PATHS(G,w,s)
topologically sort the vertices of G
INITIALIZE-SINGLE-SOURCE(G,s)
for each vertex u, taken in topologically sorted order
    for each vertex v in G.Adj[u]
    RELAX(u,v,w);

Dijkstra算法

设置一个顶点集合$S$,从长度为$1$的路径开始,依次将最短估计路径上的顶点u加到集合中,并对顶点$u$的出边进行松弛操作,直到所有顶点都被加到集合中,即可得到一条权值最短的路径

如果通过邻接矩阵存储边权,且每次加入新顶点后对其出边进行松弛操作,之后遍历数组找到下一个入集合的顶点,其时间复杂度为$O(V^{2})$;如果通过优先权队列进行优化,每次通过最小堆的方式找下一个入集合的顶点,其时间复杂度为$O((V+E)\centerdot lgV)$,若所有顶点都从源点可达,则为$O(E\centerdot lgV)$

由于Dijkstra算法是由权值小的路径逐渐递增至权值更大的路径,假设由$w(s,u)=3,w(s,v)=4,w(v,u)=-5$,则由$s$到$u$最短路径为$-1$,但是由于$u$先被加入到集合中,因此得到$\delta(s,u)=3$的错误结果,因此Dijkstra算法无法保证有负权边图最短路径的计算结果的正确性

/*
* 单源最短路径,Dijkstra算法,邻接矩阵形式,复杂度为O(n^2)
* 求出源beg到所有点的最短路径,传入图的顶点数,和邻接矩阵cost[][]
* 返回各点的最短路径lowcost[], 路径pre[].pre[i]记录beg到i路径上的父结点,pre[beg]=-1
* 可更改路径权类型,但是权值必须为非负
*
*/
const int MAXN=1010;
#define typec int
const typec INF=0x3f3f3f3f;//防止后面溢出,这个不能太大
bool vis[MAXN];
int pre[MAXN];
void Dijkstra(typec cost[][MAXN],typec lowcost[],int n,int beg)
{
    for(int i=0;i<n;i++)
    {
        lowcost[i]=INF;vis[i]=false;pre[i]=-1;
    }
    lowcost[beg]=0;
    for(int j=0;j<n;j++)
    {
        int k=-1;
        int Min=INF;
        for(int i=0;i<n;i++)
            if(!vis[i]&&lowcost[i]<Min)
            {
                Min=lowcost[i];
                k=i;
            }
        if(k==-1)break;
        vis[k]=true;
        for(int i=0;i<n;i++)
            if(!vis[i]&&lowcost[k]+cost[k][i]<lowcost[i])
            {
                lowcost[i]=lowcost[k]+cost[k][i];
                pre[i]=k;
            }
    }
}

View Code in Github Repository

注意这里INF的取值为0x3f3f3f3f($10^9$数量级)
在进行松弛操作时有
$lowcost[i]=lowcost[k]+cost[k][i]$
如果INF设置过大,等号右边可能会产生溢出,从而导致松弛操作发生错误
因此要保证"INF加INF仍然是INF",而数0x3f3f3f3f恰好可以满足这个需求
一般题目数据都在$10^9$以内,所以这个数字很好用
并且如果以这个数字作为INF值时,可以很方便地用函数$memset$(a,0x3f,sizeof(a))将数组$a$中的值初始化为INF(因为$memset()$函数是按字节填数据的)
同样地,如果需要-INF,可以用数0xc0c0c0c0,效果与INF相似
另外,在初始化数组时,使用函数$memset()$效率很高,经测试,在数组大小为$10^9$数量级时,要比使用$for$循环逐个赋值快上百倍

/*
* 使用优先队列优化Dijkstra算法
* 复杂度O(ElogE)
* 注意对vector<Edge>E[MAXN]进行初始化后加边
*/
const int INF=0x3f3f3f3f;
const int MAXN=1000010;
struct qnode
{
    int v;
    int c;
    qnode(int _v=0,int _c=0):v(_v),c(_c){}
    bool operator <(const qnode &r)const
    {
        return c>r.c;
    }
};
struct Edge
{
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector<Edge>E[MAXN];
bool vis[MAXN];
int dist[MAXN];
void Dijkstra(int n,int start)//点的编号从1开始
{
    memset(vis,false,sizeof(vis));
    for(int i=1;i<=n;i++)dist[i]=INF;
    priority_queue<qnode>que;
    while(!que.empty())que.pop();
    dist[start]=0;
    que.push(qnode(start,0));
    qnode tmp;
    while(!que.empty())
    {
        tmp=que.top();
        que.pop();
        int u=tmp.v;
        if(vis[u])continue;
        vis[u]=true;
        for(int i=0;i<E[u].size();i++)
        {
            int v=E[tmp.v][i].v;
            int cost=E[u][i].cost;
            if(!vis[v]&&dist[v]>dist[u]+cost)
            {
                dist[v]=dist[u]+cost;
                que.push(qnode(v,dist[v]));
            }
        }
    }
}
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}

View Code in Github Repository

差分约束

一个差分约束系统$S$中有多个变量$x_{i},i \in[1,n]$,变量之间满足若干个关系式: $x_{i}-x_{j}\le b_{k},1\le i,j\le n$

观察到上述关系式可以变形为三角不等式的形式$x_{i}\le x_{j}+b_{k}$,由此可以想到用松弛技术来解决。其中 $V={v_{0},v_{1}...,v_{n}}$
$E={(v_{i},v_{j}):x_{j}-x_{i}\le b_{k}是一个约束条件}\bigcup {(v_{0},v_{1}),(v_{0},v_{2}),...,(v_{0},v_{n})}$

构造这样的一个有向约束图(注意图中不能包含负环回路),加入$v_{0}$是因为考虑到其余顶点中可能存在不可达的顶点。 之后通过Bellman-Ford算法求出最短路径,则有$x_{i}=\delta(v_{0},v_{i})$

注意到如果所有的$b_{k}$均为正值时,得到的所有解为$x_{i}=0$

通过Bellman-Ford算法计算最短路径,通过邻接表存储约束图,那么时间复杂度为$O((n+1)(n+m))$,其中$n$为变量个数,$m$为约束条件个数

顶点对间最短路径问题

基于矩阵乘法的动态规划

$$l_{ij}^{(m)}= \begin{cases} 0& \text{如果$i=j$}\\ \infty & \text{如果$i\not=j$} \end{cases}$$

我们需要比较$l_{ij}^{(m-1)}$的最小值和从$i$到$j$最多$m$条边组成的路径的最小权重,有:

$$l_{ij}^{(m)}=min(l_{ij}^{(m)},min_{1\le k\le n}{l_{ik}^{(m-1)+w_{kj}}})=min_{1\le k\le n}{l_{ik}^{(m-1)}+w_{ij}}$$
对于所有的$j$有$w_{jj}=0$

这里的最短路径都是简单路径,所以最长为$n-1$,因此$\delta(i,j)=l_{ij}^{(n-1)}$

  1. 按自底向上的方式计算一个最优解的值

输入矩阵$W=(w_{ij})$,计算出矩阵$L^{(n-1)}$,其中$L^{(1)}=W$

设有矩阵$C=A\times B$,对于$C$中的每一项,都有$c_{ij}=\sum_{k=1}^na_{ik}\centerdot b_{kj}$

将运算符做如下替换,即可得到计算最短路径的算式

$min\to +$ $+\to \centerdot $

我们用矩阵"乘法"的形式来表示矩阵$W,L$之间的关系:

$L^{(n-1)}=L^{(n-2)}\centerdot W=L^{(n-3)}\centerdot W^2=...=W^{n-1}$

我们已经知道:对于所有的$m\ge n-1$,有$L^{(m)}=L^{(n-1)}$ 由于$2^{\lceil lg(n-1)\rceil}\ge n-1$,因此只要用快速幂算出$L^{2^{\lceil lg(n-1)\rceil}}$即可

在使用“矩阵乘法”的方法扩展一条边时,时间复杂度为$O(V^3)$,而求出$L^{(V-1)}$又需要进行$O(V)$次矩阵乘法,因此总的时间复杂度为$O(V^4)$,相当于在稠密图中对每一个顶点执行一次Bellman-Ford算法,复杂度为$O(V^2\centerdot E)$。而经过快速幂优化之后复杂度可以达到$O(V^3\centerdot lgV)$

Floyd-Warshall算法

$$d_{ij}^{(k)}= \begin{cases} w_{ij} & \text{如果$k=0$}\\ min(d_{ij}^{(k-1)},d_{ik}^{(k-1)}+d_{kj}^{(k-1)}) & \text{如果$k\ge 1$} \end{cases}$$

因为所有中间结点均处于集合{$1,2,...,n$}中,因此矩阵$D^{(n)}=(d_{ij}^{(n)})$即为所求,即$d_{ij}^{(n)}=\delta (i,j)$.
3. 按自底向上的方式计算一个最优解的值
$D^{(k)}$的取值依赖于$D^{(k-1)}$,输入权重矩阵$W$,递归计算得出$D^{(n)}$即可

时间复杂度为$O(V^3)$,空间复杂度为$O(V^2)$

在计算$D^{(k)}$的同时计算前驱矩阵$\Pi^{(k)}$,$\pi_{ij}^{(k)}$为从$i$到$j$的所有中间结点都在{$1,2,...,k$}中的最短路径上$j$的前驱节点 因此:

$$\pi_{ij}^{(0)}=\begin{cases}NIL & \text{若$i=j$或$w_{ij}=\infty$}\\ i & \text{若$i\not=j$且$w_{ij}<\infty$}\end{cases}$$

与最短路径的计算相似,我们可以这样递归定义$\pi_{ij}^{(k)}$:

$$\pi_{ij}^{(k)}=\begin{cases} \pi_{ij}^{(k-1)} & \text{若$d_{ij}^{(k-1)}\le d_{ik}^{(k-1)}+d_{kj}^{(k-1)}$}\\ \pi_{kj}^{(k-1)} & \text{若$d_{ij}^{(k-1)}> d_{ik}^{(k-1)}+d_{kj}^{(k-1)}$}\end{cases}$$

最终通过矩阵$\Pi^{(n)}$可以得到任意两节点之间的一条最短路径

/*
 * 顶点间最短路径floyd_warshall算法,复杂度O(V^3)
 */
const int INF=0x3f3f3f3f;
const int MAXN=1010;
int dist[MAXN][MAXN];//存储最短路径的矩阵
void init_dist() {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i==j) dist[i][j]=0;
            else dist[i][j]=INF;
        }
    }
}
void floyd_warshall(int n)//n为顶点数
{
    for(int k=1;k<=n;k++) {
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=n;j++) {
                if(dist[i][j]>dist[i][k]+dist[k][j]) 
                    dist[i][j]=dist[i][k]+dist[k][j];
            }
        }
    }
}

Johnson算法

它将Dijkstra算法和Bellman-Ford算法作为子程序,首先通过Bellman-Ford算法判断有无负环,再对所有顶点进行一次Dijkstra算法,通过重赋权的方式将所有边权化为正,计算完成后再进行还原,具体分为以下几步:

  1. 与差分约束的解决方法相同,在现有图上加一个顶点$s$和从$s$到各顶点的权值为$0$的边,保证每个顶点都可达
  2. 运行Bellman-Ford算法判断是否有负权回路,若没有则计算出由顶点$s$到其余各顶点的最短距离$\delta(s,v)$
  3. 若没有负权回路,赋值 $h(v)=\delta (s,v),v\in V$ 并为所有的边赋新的权值 $\hat{w}(u,v)=w(u,v)+h(u)-h(v),(u,v)\in E$
  4. 对除顶点$s$外的所有顶点运行Dijkstra算法计算单源最短路径$\hat{\delta}(u,v)$,再还原为实际的最短路径权重: $d_{uv}=\hat{\delta}(u,v)+h(v)-h(u)$
  5. 最终得到的矩阵$D=(d_{uv})$即为所求

  6. 复杂度

时间复杂度取决于Dijkstra算法所使用的数据结构,使用邻接表和优先队列优化可以达到$O(VElgV)$,应用于稀疏图要好于Floyd-Warshall算法

const int INF=0x3f3f3f3f;
const int MAXN=510;
struct Edge {
    int v,cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
};
vector <Edge>E[MAXN];
void addedge(int u,int v,int w) {
    E[u].push_back(Edge(v,w));    
}
int dist[MAXN];
bool vis[MAXN];
int cost[MAXN][MAXN];
void init_cost(int n) {
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            if(i==j) cost[i][j]=0;
            else cost[i][j]=INF;
        }
    }
}
void johnson() {
    int h[MAXN];
    memset(h,0,sizeof(h));
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) {
        int u,v,cost;
        scanf("%d%d%d",&u,&v,&cost);
        addedge(u,v,cost);
    }
    for(int i=1;i<=n;i++) addedge(0,i,0);
    if(!spfa(n)) return 0;//这里用spfa算法判断负权边,若有负权边,返回false,计算出的最短路径保存在dist数组中  
    for(int i=0;i<=n;i++) {
        h[i]=dist[i];
    }
    for(int u=0;u<=n;u++) {
        for(int i=0;i<E[u].size();i++) {
            int v=E[u][i].v;
            E[u][i].cost=E[u][i].cost+h[u]-h[v];            
        }
    }
    init_cost(n);
    for(int i=1;i<=n;i++) {
        Dijkstra(n,i);//i为源点,到各点的最短路径存在数组dist中
        for(int j=1;j<=n;j++) {
            if(i!=j) cost[i][j]=dist[j]+h[j]-h[i];
        }
    }
//最终结果存在cost数组中
}