Skip to content

Latest commit

 

History

History
executable file
·
216 lines (174 loc) · 8.21 KB

第四章.md

File metadata and controls

executable file
·
216 lines (174 loc) · 8.21 KB

第四章 最短路径

定义δ(s,v)为顶点s到v的最短路径。

三角不等式：δ(s,v)≤δ(s,u)+edge(u,v)。

松弛操作：

Relax(int u,int v){
	dist[v] = min(dist[v],dist[v]+edge(u,v));
}

##4.1 Dijkstra 常用于单源最短路径计算，适用于边权非负图。Dijkstra的最简单实现时间复杂度为O(V^2 )。 堆优化后可达O((V+E)lg(v))。

定义

  1. 定义src为源点
  2. 定义集合S为已扩展的顶点集，即该集合中任意顶点u已经求出src->u的最短路径。
  3. 定义集合T为待扩展的顶点集。
  4. 定义dist[v]为从源点src经过集合s的路径中到达v的最短路径。

算法过程

  1. 从源点src开始更新src能直接到达的节点距离，用dist保存。
  2. 从dist中找到一点未被访问过且其dist最小的节点cur，并标记cur已被访问。
  3. 如果cur为终点ter，算法结束返回dist[ter]。
  4. 否则更新cur能直接到达的节点to距离，dist[to] = min(dist[to],dist[cur]+edge<cur,to>)。
  5. 重复步骤（2-4）n-1次

如果集合T中顶点v的dist最小，则v是下一个需要扩展的顶点。（三角不等式）假设v不是下一个扩展点，则∃u∈T，使得dist[u]+e<u,v> <= dist[v]，但是dist[v]=min{dist[x]│x∈T}，即dist[v] <= dist[u]，与假设矛盾。

代码

int dijkstra(int src,int ter){//src源点,ter终点
vist[src] = 1;
dist[src] = 0;
for(int i = head[src];i != -1;i = edge[i].pre ){
        dist[edge[i].cur] = edge[i].w;      //dist[x]保存从源点到节点x当前最短距离
}
for(int i = 1;i < n;i ++){
    int cur = 0,Min = inf;
    for(int j = 1;j <= n;j ++){
        if(!vist[j] && dist[j] < Min){
            Min = dist[j];
            cur = j;
        }
    }
    vist[cur] = 1;
    if(cur == ter)return dist[cur];
    //当ter被标记为访问过时，说明当前dist[ter]已经为src到ter的最短距离
    for(int j = head[cur];j != -1;j = edge[j].pre ){
        int to = edge[j].cur;
        if(!vist[to]){
            dist[to] = min(dist[to],dist[cur] + edge[j].w);
        }
    }
}
return dist[ter];
}

堆优化

简单分析可知，外层循环n次是必须的，而内层求最小dist的顶点采用最小堆可以将时间复杂度从O(V)降为O(logV)。

int dijkstra(int src,int ter){
vist[src] = 1;
dist[src] = 0;
priority_queue<node>q;
/*
struct node{
int v,dist;//顶点和距离
node(int vv,int ddist){v=vv,dist=ddist;}
bool operator<(const node &A)const{return dist > A.dist;}//最小优先
};
*/
q.push(node(src,0));
int cur = src;
for(int i = 0;i < n;i ++){
    for(int j = head[cur];j != -1;j = edge[j].pre ){
        int to = edge[j].cur;
        if(!vist[to] && dist[to]>dist[cur]+edge[j].w){
            dist[to] = dist[cur] + edge[j].w;
            q.push(node(to,dist[to]));
        }
    }
    while(!q.empty()&&vist[q.top().v]){
        q.pop();
    }
    cur = q.top().v;q.pop();
    vist[cur] = 1;
    if(cur == ter)break;
}
return dist[ter];
}

4.2 Floyd

解决任意两点间的最短路径问题，适合于稠密图。

基本思想

dist[u][v]：u->v 的最短路径 采用动态规划方法： 对于任意两个顶点u、v，假设当前u、v的最短路径为dist(u->v)，当在u、v之间加入新的一个顶点t时，u、v之间可以构造一条新路dist(u->t)+dist(t->v)，显然按照最优原则，我们会选择dist(u->v)和dist(u->t)+dist(t-v)中最短的一条路径并更新dist(u->v)。 对u、v、t依次枚举，算法最终时间复杂度为O(v^3)。

代码

int floyd(int src,int ter){
for(int k = 1;k <= n;k ++)
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
        {
            dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
        }
return dist[src][ter];
}

4.3 Bellman-Ford

循环V-1次对每条边做松弛操作，每次松弛会让dist[v]更加紧确于δ(s,v)。

适用于有负权边的图，可以判断负权环，时间复杂度为O(VE)。

def Bellman-Ford(src)
dist[src] = 0
for i = 1 to V-1
    for edge(u,v) in range E
        Relax(u,v)
for edge(u,v) in range E
    if dist[v] > dist[u] + edge(u,v)
        return false
return true

4.4 SPFA

SPFA是对Bellman-Ford的队列优化。适用范围与Bellman-Ford算法相同，也能判断负环。

思想：
下次松弛的前导节点必是当前松弛的节点。如果不是，则该前导节点对下次松弛是没用意义的，因为该前导节点的估计距离未被更新过。所以可以用一个队列记录当前被松弛的节点。

时间复杂度为O(KE)，k是个比较小的系数，并且在绝大多数的图中，k<=2。

负权环判定：若一个顶点入队次数超过V，则有负权环。

算法过程：

def spfa(src,ter)
create queque q
q.push (src)
dist[src] = 0
while q is not empty
    cur = q.front()
    q.pop_front()
    for to in range adj[cur]
        if Relax(cur,to) and to is not in q
                q.push(to)
return dist[ter]

SLF优化代码

int spfa(int src,int ter){
deque<int>q;
q.push_back(src);
inqueue[src] = 1;//标记当前顶点是否在队列中
dist[src] = 0;
while(!q.empty()){
    int cur = q.front();
    q.pop_front();
    inqueue[cur] = 0;
    for(int i = head[cur];i != -1;i = edge[i].pre){
        int to = edge[i].cur;
        if(dist[to] > dist[cur]+edge[i].w){//松弛
            dist[to] = dist[cur] + edge[i].w;
            if(!inqueue[to]){
                inqueue[to] = 1;
                if(!q.empty()&&dist[to]<dist[q.front()])//SLF优化
                    q.push_front(to);
                else q.push_back(to);
            }
        }
    }
}
return dist[ter];
}

4.5 无向无环图两点最远路径

两次BFS找无向无环图中最远两点路径:

  1. 第一次找离某一点（这个自己定）最远的点A
  2. 第二次找离点A最远的点B，AB的路径即为最远路径

4.6 双调欧几里得旅行商问题

问题描述：

解法：

我们设dp[i][j]为从点i出发从右往左走到最左端（A路），然后从左往右走到点j（B路）的最短路径，这条路径满足以下几点：

  1. 路径上没有重复访问的点；
  2. 从最左端到max(i,j)之间的每个点都被访问过；
  3. 该条路径是符合1,2两点的最短路径

实际上dp[i][j]和dp[j][i]是相同的，所以以下我们将只对i>j 的情况进行讨论。当i==j 时，i点在路径上被重复访问，不符合题设。

  1. 当j < i – 1时，由第二点可得，点i-1必然在dp[i][j]的路径上，又由于j<i-1的，即在dp[i][j]上不可能存在路径j->i-1（j在dp[i][j]上已经是终点），那么边w<i-1,i>就必然在该路径上，所以此时的状态为dp[i][j]=dp[i-1][j]+w<i-1,i>;
  2. 当j == i - 1时，此时不确定点k(1<=k<j）是在A路，还是B路，由于A路和B路在数学上是对等的，从另一个角度说，我们不确定哪点是在A路，此时，用状态dp[i][j]=min(dp[k][j]+w(k,i)) 确定。

4.7 差分约束

差分约束系统：由｀n｀个变量和｀m｀个约束条件组成的约束系统。每个约束条件形如：｀x_i-x_j≤b_k｀，其中｀1≤i，j≤n，1≤k≤m｀。这个系统可记为｀Ax=b｀。

最短路径解法：

对于每个约束条件，可以转换为x_i≤x_j+b_k，此时约束条件形如δ(u)≤δ(v)+edge(v,u)的三角不等式。只要将i，j作为图的顶点，建j -> i权值为b_k的有向边，该图G称为约束图。应用最短路算法，最终求出最短路径即为一组可行解。但是如果约束图中存在负权环，那么该差分约束系统不存在可行解。

习题

  • hdu 1384 Intervals
  • hdu 1531 King *　hdu 1534 Schedule Problem