多条最短路径问题再探-使用Dijkstra+DFS选出并输出最优路径

发布于 / 数据结构与算法 / Comments Off on 多条最短路径问题再探-使用Dijkstra+DFS选出并输出最优路径

0x00、复杂多条最短路径问题

前面我们提到过多条最短路径类问题,诸如"新增边权"、"新增点权"、"求最短路径条数(新增计数器)"等类问题,这里面新增的内容被我们称为"第二标尺"。(传送门:多条最短路径情况

在多条最短路径类问题上,一般的出题套路会围绕着"和"来探讨,例如让新增边权之和最小,新增点权之和最大,路径条数最小等等。但是不排除问题不单纯的让求"和",这时问题会变得比较复杂,用之前的方式就无法得到正确的结果,因为题目不一定要求满足最优子结构。下面介绍一种Dijkstra+DFS的思路来解决这种逻辑较为复杂的问题

Dijkstra+DFS的思路很好理解,在之前的解决方案里,我们遵循"发现最短路径就更新,发现相同路径就比较第二标尺并累加",而使用Dijkstra+DFS的思路是"在Dijkstra算法里面记录下所有的最短路径,然后使用DFS遍历所有路径,选出第二标尺最优的路径"。下面具体说说该如何实现

0x01、Dijkstra生成前驱数组

先说说Dijkstra求解出的最短路径怎么输出吧!首先引入前驱数组的定义:

    前驱数组,就是 数组的 每个元素 都存放着  元素代表的节点 的前驱

如果只是存放单个前驱,我们定义一个一维数组做为前驱数组就好了

int pre[MAXN];

在编写Dijkstra函数的时候,我们要在更新数组的部分稍作修改:

if(发现以u做中介点,走向v,可以获得更好的路径){
    pre[u] = v;    //记录前驱
    存放最短距离数组[v] = 存放最短距离数组[v] + 邻接矩阵[u][v];
}

接着我们在Dijkstra运行完毕后就可以使用DFS算法输出这条最短路径经历了哪些节点了:

void DFS(int p){
    if(p == 起点){    //起点是递归边界,这是因为我们从终点往前遍历。
                     //从终点往前遍历最方便,这是因为我们数组里保存的都是前驱
        printf(起点);
        return;
    }
    DFS(pre[p]);    //如果p不是递归边界,我们递归遍历p的前驱
    printf(p);
}
DFS(终点);    //DFS入口

以上就是只记录一条路径的情况下,怎么使用DFS+前驱数组输出路径,下面看看记录多个路径的情况

这里我们的前驱不能使用一维数组了,因为我们要记录多个路径就可能产生多个前驱。我们使用变长数组vector

vector<int> pre[MAXN];

这样pre数组的每个单元都可以存放多个值,对于每一个节点v而言,就可以存放v的所有能产生最短路径的前驱结点。

比如说下面的这个图,现在要求找到 A 点到 E 点的最短路径:

我们的pre数组内部存储是这样的:

pre[A] = {A};
pre[B] = {A,C};
pre[C] = {A};
pre[D] = {B};
pre[E] = {B,C};

我们使用DFS遍历这个数组,就可以获得全部最短路径:

{A, B, E}、{A, C, E}、{A, C, B, E}

在Dijkstra算法中,你可以无需看第二标尺,专心求解前驱数组。里面更新数组思路为:

if(发现距离更短的路径){
    更新存放最短路径的数组;
    清空这个点对应的前驱数组;
    将这个点存入前驱数组
}else if(发现距离相同的路径){
    将这个点存入前驱数组
}

其他的思路与一般Dijkstra算法一样。

用C语言实现就是:

vector<int> pre[MAXN];
void Dijkstra(int s){    //s为起点
    fill(d, d + MAXN, INF);    //d为存放最短路径值的数组,INF为一个很大的数
    d[s] = 0;    //初始化d[s]
    for(int i = 0; i < n; i++){    //n为顶点个数。
        /*开始找路径最短的点*/
        int u = -1, MIN = INF;    //u为下表,MIN为存放路径最短的值
        for(int j = 0; j < n; j++)
            if(visited[j] == false && d[j] < MIN)
                u = j, MIN = d[j];
        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];
                    pre[v].clear();
                    pre[v].push_back(u);
                }else if(d[u] + G[u][v] == d[v]){
                    pre[v].push_back(u);
                }
            }
        }
    }
}

这样,我们就完成了前驱数组的创建。接着我们使用DFS,在路径最短的条件下找到使第二标尺。

0x02、DFS找到最优路径

前面说过了前驱数组,下面我们要做的就是使用DFS遍历前驱数组,找到第二标尺最优的路径。

DFS算法最大的特征是递归,递归函数一般分为两部分:递归边界和递归式,那么我们这里面的递归边界和递归式分别是什么呢?

很显然,我们从终点开始遍历(因为我们保存的是前驱数组。所以必须从终点开始遍历),遍历到起点就是递归边界了;而递归式,把当前访问的节点对应的vector容器遍历一遍,每一个节点都递归一次就好啦

代码如下:

int bestValue;    //存放第二标尺最优值
vector<int> pre[MAXN];    //前驱节点数组
vector<int> path;    //存放最优路径
vector<int> tempPath;    //存放临时路径

void DFS(int v){    //v为当前访问的节点
    tempPath.push_back(v);    //将v加入临时路径
    //DFS的"死胡同",递归边界
    if(v == startPoint){    //遍历到了终点
        int value;                //在此计算第二标尺
        if(value比bestValue更优){    //比较当前第二标尺与之前最优的第二标尺,确定是不是一条更优的路径
            bestValue = value;    //更新最优值
            path = tempPath;       //更新最优路径
        }
    }
    //DFS的"岔路口",递归式
    else{            //v != startPoint,没遍历到终点
        for(int i = 0; i < pre[v].size(); i++){//枚举容器内的所有前驱结点
            DFS(pre[v][i]);                //然后依次遍历
    }
    tempPath.pop_back();    //本节点找完了,删掉。以便遍历其他的
}

转载原创文章请注明,转载自: 斐斐のBlog » 多条最短路径问题再探-使用Dijkstra+DFS选出并输出最优路径
评论已关闭