Dijkstra算法进阶--多条最短路径情况

发布于 / 数据结构与算法 / 1 条评论

在解Dijkstra的问题时,常常会遇到最短路径不止一条的情况。就像这样:


图中绿色为边,绿色字体为边权,灰色字体为点权,黑色字体为顶点编号。

如果我们计算从0到2的最短路径,答案是有两条,0--1--2和0--2

0、出题套路

在考察这类问题时,通常分三种情况

  1. 给每条边在第一边权的基础上增加一个边权,即"第二边权",要求在第一边权最短的情况下,让第二边权最短(或最大)。

    例如:第一边权是距离,第二边权是路费。要求在距离最短的情况下求出路费最短的路径

  2. 给每一个点加一个点权(就像上面给出的图那样),要求在边权最短的情况下让点权之和最大(或最小)

    例如:边权是距离,点权是到达城市能收集到的物资。要求路径最短的情况下收集到的物资最多

  3. 直接问有多少条最短路径

对于这三种出题方法,只需要增加一个数组存放新增边权或点权或最短路径条数。然后在之前发表的文章"最短路径 - 迪杰斯特拉(Dijkstra)算法详解"的代码中,对寻找最小值的循环稍作修改即可

下面均以邻接矩阵为例。邻接表的情况可以自行修改。

1、新增边权

例如原来的边权表示距离新增的边权表示路费。假设s是起点,我们定义一个二维数组:cost[u][v] 表示 顶点u->顶点v 的消费(这个一定是题目给出的),接着增加一个数组 c[u],表示起点s到顶点u的最少消费。初始化的时候令c[s]=0,这是因为起点到自己本身是不需要消费的。数组c的其余值都是INF,在每次找最小点的时候更新数组c的值,就可以达到寻找最少消费的目的。

代码如下:

/*@@@@@@@ 以下都是原来的代码,不需要修改 @@@@@@@*/
int n, G[MAXN][MAXN];    //n为顶点数,G为邻接矩阵
int d[MAXN];    //d数组存储起点到达各点最短路径长度
bool visited[MAXN] = {false}; //标记数组,前面说过了
 
/*Dijkstra算法。s为起点的编号*/
void Dijkstra(int s){
    fill(d, d+MAXV, INF);    //将数组d全部赋值为很大的数
    d[s] = 0;    //起点到自己本身的距离为0
    for(int i = 0; i < n; i++){    //循环n次,n是顶点数,处理每一个点
        int u = -1, MIN = INF;    //u存放"用来找数组d中最小值的下标",MIN存放"数组d中的最小值"
        for(int j = 0; j < n; j++){   //枚举每一个点
            if(visited[j] == false)    //如果这个点没有处理过
                if(d[j] < MIN){         //并且这个点到顶点的距离比MIN小(MIN的初始值很大)
                    u = j;        //让u等于最小值的下标
                    MIN = d[j];   //MIN等于d中的最小值
                }
        }
        //如果u==-1,说明没有找到,也就是剩下的顶点与起点s不连通,我们直接终止函数
        if(u == -1) return;
        //如果找到了最小值的那个点,进行后续步骤
        visited[u] = true;    //标记这个点为已经访问过
        for(int v = 0; v < n; v++){    //枚举每一个点
        
        /*@@@@@@@  这个循环的里面需要进行修改,加上计算路费的代码 @@@@@@@*/
        
            if(visited[v] == false && G[u][v] != INF){    //如果这个点没有处理过,且有路可走
                    if(d[u]+G[u][v]<d[v]){ //如果以最小值点为中介点可以找到更短路径
                        c[v] = c[u] + cost[u][v];    //更新到达v的消费 = 到达u的消费 + u和v之间的路费
                        d[v] = d[u] + G[u][v];    //更新d[v],使得d[v]最小
                    }else if(d[u] + G[u][v] == d[v] && c[u] + cost[u][v] < c[v]){
                        //以最小值点为中介点的路径与之前找到的最短路径相同,但是路费却更少的情况
                        c[v] = c[u] + cost[u][v];    //更新到达v的消费 = 到达u的消费 + u和v之间的路费
                    }
            }
            
        /*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/   
            
        }
    }
}

我们在更新最短路径的时候,同时更新了所需路费。如果最短路径相同的时候,我们判断了路费的解是否最优。在路径不是最短的时候,直接忽略,这是因为一切大前提是路径最短。一切都必须确保路径是最短的,在这个基础上才可以考虑费用等其他的。

如果题目要求计算第二边权最大,只需要将"c[u] + cost[u][v] < c[v]"这一句的"<"改为">"

2、新增点权

例如原来边权表示距离新增点权表示城市中能收集到的物资数量。使用数组 weight[u] 表示点u的点权(题目给出),并新增一个用来记录数据w[u],表示起点s到顶点u可以收集到的最大物资量。初始化的时候只有w[s]和weight[s](题目给出)其余w[]均为0。和上面增加边权的方式一样,我们仍然在老位置修改代码:

/*@@@@@@@ 以下都是原来的代码,不需要修改 @@@@@@@*/
int n, G[MAXN][MAXN];    //n为顶点数,G为邻接矩阵
int d[MAXN];    //d数组存储起点到达各点最短路径长度
bool visited[MAXN] = {false}; //标记数组,前面说过了
 
/*Dijkstra算法。s为起点的编号*/
void Dijkstra(int s){
    fill(d, d+MAXV, INF);    //将数组d全部赋值为很大的数
    d[s] = 0;    //起点到自己本身的距离为0
    for(int i = 0; i < n; i++){    //循环n次,n是顶点数,处理每一个点
        int u = -1, MIN = INF;    //u存放"用来找数组d中最小值的下标",MIN存放"数组d中的最小值"
        for(int j = 0; j < n; j++){   //枚举每一个点
            if(visited[j] == false)    //如果这个点没有处理过
                if(d[j] < MIN){         //并且这个点到顶点的距离比MIN小(MIN的初始值很大)
                    u = j;        //让u等于最小值的下标
                    MIN = d[j];   //MIN等于d中的最小值
                }
        }
        //如果u==-1,说明没有找到,也就是剩下的顶点与起点s不连通,我们直接终止函数
        if(u == -1) return;
        //如果找到了最小值的那个点,进行后续步骤
        visited[u] = true;    //标记这个点为已经访问过
        for(int v = 0; v < n; v++){    //枚举每一个点
        
        /*@@@@@@@  这个循环的里面需要进行修改,加上计算物资量的代码 @@@@@@@*/
        
            if(visited[v] == false && G[u][v] != INF){    //如果这个点没有处理过,且有路可走
                    if(d[u]+G[u][v]<d[v]){ //如果以最小值点为中介点可以找到更短路径
                        w[v] = w[u] + weight[v];    //更新到达v积累的物资 = 到达u积累的物资 + 在v处能积累下的物资
                        d[v] = d[u] + G[u][v];    //更新d[v],使得d[v]最小
                    }else if(d[u] + G[u][v] == d[v] && w[u] + weight[v] > w[v]){
                        //以最小值点为中介点的路径与之前找到的最短路径相同,但是路费却更少的情况
                        w[v] = w[u] + weight[v];    //更新到达v积累的物资 = 到达u积累的物资 + 在v处能积累下的物资
                    }
            }
            
        /*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/   
            
        }
    }
}

如果题目要求计算点权最小,只需要将"w[u] + weight[v] > w[v]"这一句的">"改为"<"

3、计算最短路径条数

这种题目更好办,直接在有相同路径长度的判断上加一个累加计数器即可。

当发现新的最短路径时,说明当前层的最短路径只有这一条,我们只需要继承上一级的最短路径条数。

当发现有最短路径与上一级的路径长度相同时,说明这一层最短路径不知这一条,我么要进行累加。

我们定义一个数组num[u]表示起点s到顶点u的最短路径条数。在起始状态,num[s]=1,num数组其他的值全部为0,接着还是在老地方,修改代码:

/*@@@@@@@ 以下都是原来的代码,不需要修改 @@@@@@@*/
int n, G[MAXN][MAXN];    //n为顶点数,G为邻接矩阵
int d[MAXN];    //d数组存储起点到达各点最短路径长度
bool visited[MAXN] = {false}; //标记数组,前面说过了
 
/*Dijkstra算法。s为起点的编号*/
void Dijkstra(int s){
    fill(d, d+MAXV, INF);    //将数组d全部赋值为很大的数
    d[s] = 0;    //起点到自己本身的距离为0
    for(int i = 0; i < n; i++){    //循环n次,n是顶点数,处理每一个点
        int u = -1, MIN = INF;    //u存放"用来找数组d中最小值的下标",MIN存放"数组d中的最小值"
        for(int j = 0; j < n; j++){   //枚举每一个点
            if(visited[j] == false)    //如果这个点没有处理过
                if(d[j] < MIN){         //并且这个点到顶点的距离比MIN小(MIN的初始值很大)
                    u = j;        //让u等于最小值的下标
                    MIN = d[j];   //MIN等于d中的最小值
                }
        }
        //如果u==-1,说明没有找到,也就是剩下的顶点与起点s不连通,我们直接终止函数
        if(u == -1) return;
        //如果找到了最小值的那个点,进行后续步骤
        visited[u] = true;    //标记这个点为已经访问过
        for(int v = 0; v < n; v++){    //枚举每一个点
        
        /*@@@@@@@  这个循环的里面需要进行修改,加上计算物资量的代码 @@@@@@@*/
        
            if(visited[v] == false && G[u][v] != INF){    //如果这个点没有处理过,且有路可走
                    if(d[u]+G[u][v]<d[v]){ //如果以最小值点为中介点可以找到更短路径
                        d[v] = d[u] + G[u][v];    //更新d[v],使得d[v]最小
                        num[v] = num[u];  //如果走到了这个if里面,说明这个岔路口只有这一种最短路径。继承之前路径数即可
                    }else if(d[u] + G[u][v] == d[v]){//如果最短距离相同
                        num[v] += num[u];    //执行累加
                    }
            }
            
        /*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/   
            
        }
    }
}

4、更变态的情况(三种情况叠加)

假如出题老师非常非常厉害,上面三种情况包含了两种,甚至三种都包含了!

怎么办!

还是老地方,多加个判断语句就行了!

还是不会?做为一个良心博主,继续给你举例子:

例如要求在路径最短的情况下,找出点权最大的情况,同时求出最短路径条数。

老地方,把for语句里面的 if语句 改成这个样子:

if(visited[v] == false && G[u][v] != INF){    //如果这个点没有处理过,且有路可走
    if(d[u]+G[u][v]<d[v]){ //如果以最小值点为中介点可以找到更短路径
        d[v] = d[u] + G[u][v];    //更新d[v],使得d[v]最小
        num[v] = num[u];          //继承之前路径数
        w[v] = w[u] + weight[v];  //更新点权
    }else if(d[u] + G[u][v] == d[v]){//如果最短距离相同
        num[v] += num[u];    //执行累加
        if(w[u] + weight[v] > w[v]){
            w[v] = w[u] + weight[v];    //更新总点权
        }
    }
}

转载原创文章请注明,转载自: 斐斐のBlog » Dijkstra算法进阶--多条最短路径情况
  1. winsr

    非常感谢大佬的总结,对我真的有很大的帮助,谢谢!