动态规划求图中所有顶点对的最短路径
程序员文章站
2024-03-15 18:54:24
...
动态规划求所有点对最短路径
- 问题描述
应用动态规划算法求有向图中每一对顶点的赋权最短路径。
- 从Dijkstra算法中思考
Dijkstra算法采用贪心的策略,指定从顶点s开始分阶段进行。图中的每个顶点最终都会被选作中间顶点。如果当前所选顶点是,那么对于的每个邻接点,,其中为连接权值。该公式说明,从s到w的最短路径是前面知道的从s到w的距离,或者是从s先到v最短然后v再到w总路径最短。
- 动态规划的思路
将定义为从顶点到顶点借助前个顶点作为中间顶点的最短路径。则根据定义:即直接等于连接权值。而则表示图中,到的最短路径(可以借助所有顶点作为中间顶点)。
当时,有两种可能的结果:一是不借助第个顶点作为中间顶点的最短路径;二是借助第个顶点作为中间顶点由和形成的最短路径,其中每条路径只借助前个顶点作为中间顶点。
用公式描述为:
从公式可以看出,第k阶段只依赖于第k-1阶段,因此每个阶段需要保存一个大小的矩阵。
- 与Dijkstra算法比较
Dijkstra算法的时间复杂度为,对稀疏图运行更快。动态规划算法求最短路径时间复杂度为,因为紧凑的循环,对稠密的图会运行更快。
- 简单代码
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: 数据结构与算法分析