欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

动态规划求图中所有顶点对的最短路径

程序员文章站 2024-03-15 18:54:24
...

动态规划求所有点对最短路径

  • 问题描述

应用动态规划算法求有向图G=(V,E)中每一对顶点的赋权最短路径。

  • 从Dijkstra算法中思考

Dijkstra算法采用贪心的策略,指定从顶点s开始分阶段进行。图中的每个顶点最终都会被选作中间顶点。如果当前所选顶点是v,那么对于v的每个邻接点wdw=min(dw,dv+cv,w),其中cv,w为连接权值。该公式说明,从s到w的最短路径是前面知道的从s到w的距离,或者是从s先到v最短然后v再到w总路径最短。

  • 动态规划的思路

Dk,i,j定义为从顶点vi到顶点vj借助前v1,v2,...,vk个顶点作为中间顶点的最短路径。则根据定义:D0,i,j=ci,j即直接等于连接权值。而D|V|,i,j则表示图G=(V,E)中,vivj的最短路径(可以借助所有顶点作为中间顶点)。

k>0时,Dk,i,j有两种可能的结果:一是不借助第k个顶点vk作为中间顶点的最短路径;二是借助第k个顶点vk作为中间顶点由vivkvkvj形成的最短路径,其中每条路径只借助前k1个顶点作为中间顶点。
用公式描述为:

Dk,i,j=min{Dk1,i,j, Dk1,i,k+Dk1,k,j}

从公式可以看出,第k阶段只依赖于第k-1阶段,因此每个阶段需要保存一个|V||V|大小的矩阵。

  • 与Dijkstra算法比较

Dijkstra算法的时间复杂度为O(|V|2),对稀疏图运行更快。动态规划算法求最短路径时间复杂度为O(|V|3),因为紧凑的循环,对稠密的图会运行更快。

  • 简单代码
void Allpairs(const int A[][7], int** Dist, vector<vector<int>> Path, int N)
{   // A为图的邻接矩阵,Dist为更新顶点间的最短距离矩阵,Path为记录路径矩阵
    int i, j, k;
    for (i = 0;i < N;i++)       // 初始化Dist和Path矩阵
    {
        for (j = 0;j < N;j++)
        {
            Dist[i][j] = A[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 (Dist[i][k] + Dist[k][j] < Dist[i][j])   // 当第k个顶点作为中间顶点使得顶点i和顶点j的路径变短,则
                {
                    Dist[i][j] = Dist[i][k] + Dist[k][j];   // 更新最短路径值
                    Path[i][k] = k;                         // 路径矩阵记录第k个顶点
                }
            }
        }
    }

}

附动态规划求图所有顶点对的最短路径C++

#include<iostream>
#include<vector>
using namespace std;
const int INF = 999999;     // 定义无穷大,此例中

void Allpairs(const int A[][7], int** Dist, vector<vector<int>> &Path, int N)
{   // A为图的邻接矩阵,Dist为更新顶点间的最短距离矩阵,Path为记录路径矩阵
    int i, j, k;
    for (i = 0;i < N;i++)       // 初始化Dist和Path矩阵
    {
        for (j = 0;j < N;j++)
        {
            Dist[i][j] = A[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 (Dist[i][k] + Dist[k][j] < Dist[i][j])   // 当第k个顶点作为中间顶点使得顶点i和顶点j的路径变短,则
                {
                    Dist[i][j] = Dist[i][k] + Dist[k][j];   // 更新最短路径值
                    Path[i][k] = k;                         // 路径矩阵记录第k个顶点
                }
            }
        }
    }

}

int main()
{
    const int N = 7;
    const int AM[N][N] = {                      // 函数指针的参数应不指定一维长度,但是其它维的参数需要指定
        {0, 2, INF, 1, INF, INF, INF},
        {INF, 0, INF, 3, 10, INF, INF},
        {4, INF, 0, INF, INF, 5, INF},
        {INF, INF, 2, 0, 2, 8, 4},
        {INF, INF, INF, INF, 0, INF, 6},
        {INF, INF, INF, INF, INF, 0, INF},
        {INF, INF, INF, INF, INF, 1, 0} };      // 图的邻接矩阵表示

    // 两种方式创建动态二维数组:1.动态分配内存    2.STL向量模板
    // 动态内存分配也有两种方式:
    int** Dist = new int*[7];   // 第一种:Dist为指向指针的指针,指向长度为7的一个指针数组(元素为整型指针)的头指针,
                                //      Dist表示指针数组的头指针,Dist+1表示指向指针数组第一个元素的指针
                                //      Dist[1]或*(Dist+1)表示指针数组的第1个元素(元素为一个整形指针)
                                //      这种表示,传递函数中的形参表示为:int** Dist
    for (int i = 0;i < 7;i++)           
    {
        Dist[i] = new int[7];   // 前面只是分配了一个一维指针数组的空间,现在要为每个指针数组的元素分配空间(即分配7个一维整型数组的空间)
    }

    //int(*Dist)[7] = new int[7][7];    // 第二种:Dist为一个指向长度为7的(子)数组(元素为整型数)的指针,而二维数组由7个这样的子数组构成,
    //                                  //     Dist表示第一个子数组的头指针,Dist+1表示第2个子数组的头指针
    //                                  //     这种表示,函数传递形参的方式为:int(*Dist)[7]

    // 使用STL标准模板库的向量创建
    // Path为一个二维嵌套向量,每个元素为一个vector<int>类型的子向量(共7个),每个子向量为7个int类型的数构成
    vector<vector<int>> Path(7, vector<int>(7));    

    Allpairs(AM, Dist, Path, 7);    // 求根据邻接矩阵求有向图的所有点的最短路径

    cout << "The Distance Matrix:\n";
    for (int i = 0; i < 7;i++)
    {
        for (int j = 0;j < 7;j++)
        {
            if (*(*(Dist + i) + j) == INF)
                cout << "INF" << "\t";
            else
                cout << *(*(Dist + i) + j) << "\t";
        }
        cout << endl;
    }
    cout << "\nThe Path Matrix:\n";
    for (int i = 0;i < 7;i++)
    {
        for (int j = 0;j < 7;j++)
        {
            cout << "V"<< Path[i][j] << "\t";
        }
        cout << endl;
    }
    for (int i = 0;i < 7;i++)
    {
        delete[] Dist[i];
    }
    system("pause");
    return 0;
}
  • 运行结果
The Distance Matrix:
0       2       3       1       3       6       5
9       0       5       3       5       8       7
4       6       0       5       7       5       9
6       8       2       0       2       5       4
INF     INF     INF     INF     0       7       6
INF     INF     INF     INF     INF     0       INF
INF     INF     INF     INF     INF     1       0

The Path Matrix:
V-1     V1      V-1     V3      V-1     V-1     V6
V-1     V-1     V-1     V3      V-1     V-1     V6
V0      V1      V-1     V3      V-1     V-1     V-1
V-1     V-1     V2      V-1     V-1     V-1     V6
V-1     V-1     V-1     V-1     V-1     V-1     V6
V-1     V-1     V-1     V-1     V-1     V-1     V-1
V-1     V-1     V-1     V-1     V-1     V-1     V-1
请按任意键继续. . .

参考资料

Mark Allen Weiss: 数据结构与算法分析