当前位置:网站首页>动态规划_每对结点间的最短路径_Floyd

动态规划_每对结点间的最短路径_Floyd

2021-07-10 16:30:06 花城1122

问题描述

\(G=(V,E)\)是一个有\(n\)个结点的带权有向图,\(w(i,j)\)是权函数

\[w(i,j)=\begin{cases} 边<i,j>上的权值 &\text{if } <i,j>\in E \\ 0 &\text{if } i=j\\ \infty &\text{if } <i,j>\notin E \end{cases} \]

每对结点间的最短路径问题是指图中任意一对结点\(i\)\(j\)之间的最短路径。

分析

Dijkstra算法要求图中的边的权为非负值,而本问题中允许边的权为负值,但不允许路径长度为负值的回路,因为若结点\(i\)到结点\(j\)的路径上存在负值回路,则意味着结点\(i\)到结点\(j\)没有最短路径。

最优子结构特性

\(G=(V,E)\)是带权有向图,L(i,j)是从结点\(i\)到结点\(j\)的最短路径长度,\(k\)是这条路径上的一个结点,\(L(i,k)\)\(L(k,j)\)分别是从\(i\)\(k\)和从\(k\)\(j\)的最短路径长度,则必有\(L(i,j)=L(i,k)+L(k,j)\),若不然,则\(L(i,j)\)代表的路径就不是最短路径。

最优解值的递推关系

\[d_{-1}[i][j]=\begin{cases} w(i,j) &\text{if } <i,j>\in E \\ \infty &\text{if } <i,j>\notin E \end{cases} \]

\[d_k[i][j]=\min\{d_{k-1}[i][j],d_{k-1}[i][k]+d_{k-1}[k][j]\},1\leq k \leq n-1 \]

其中\(d_k[i][j]\)表示从结点\(i\)到结点\(j\)的路径上,只允许包含编号不大于\(k\)的结点时,所以可能的路径中的最短路径的长度,\(d_{-1}[i][j]\)表示从\(i\)\(j\)不包含结点(直达)的长度,\(L(i,j)=d_{n-1}[i][j]\)

重叠子问题

为了计算\(d_k[i][j]\)时,必须计算\(d_{k-1}[i][j],d_{k-1}[i][k],d_{k-1}[k][j]\)

  • 邻接矩阵\(a\)存储有向图
  • 二维数组\(d\)用于保存各条最短路径的长度,其中\(d[i][j]\)存放从结点\(i\)到结点\(j\)的最短路径的长度
  • 二维数组\(path\)记录相应的最短路径,\(path[i][j]\)给出从结点\(i\)到结点\(j\)的最短路径中的前一个结点,可以反向追溯最短路径
  • 初始时\(d[i][j]=a[i][j]\)
  • \(k=0,1,...,n-1\),每次考察一个结点\(k\)
  • 在算法的第\(k\)步上应作出决策:从\(i\)\(j\)的最短路径上是否包含结点\(k\)

程序

#include<iostream>
using namespace std;

vector<vector<int> > a;//邻接矩阵
vector<vector<int> > d;//保存每对结点之间最短路径
vector<vector<int> > path;//标记函数
int n;//结点数

//创建邻接矩阵
void CreateA(){
	cin >> n;
	for(int i = 0;i < n;i ++){
		vector<int> v;
		int v1;
		for(int j = 0;j < n;j ++){
			cin >> v1;
			v.push_back(v1);
		}
		a.push_back(v);
	}
}

void allPath(){
	for(int i = 0;i < n;i ++){//初始化d
		for(int j = 0;j < n;j ++){
			d[i][j] = a[i][j];
		}
	}
	//迭代:对于点k,若i直接到j的距离大于1->k->j的距离和时,改写d[i][j]
	for(int k = 0;k < n;k ++){
		for(int i = 0;i < n;i ++){
			for(int j = 0;j < n;j ++){
				if(d[i][k]+d[k][j]<d[i][j])
					d[i][j] = d[i][k] + d[k][j];
			}
		}
	}
}
int main(){
	CreateA();
	allPath();
	return 0;
}
 

结束语

其实你并没有什么忘不掉的人,只是始终对自己那场没有结果的付出和被浪费的爱耿耿于怀。

作者:花城

版权声明
本文为[花城1122]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/huacheng1122/p/14994040.html