找回密码
 立即注册

本文来自

电脑/上网

电脑/上网

订阅|关注

致力于提供软件新闻发布,和软件知识学习,包括常用软件应用技巧及评测,创意设计相关的图文及视频教程

最短路径算法(下)——弗洛伊德(Floyd)算法

[复制链接]
230 553129131 发表于 2017-9-13 19:25:36
在这篇博客中我主要讲解最短路径算法中的Floyd算法,这是针对多源最短路径的一个经典算法。对于单源最短路径算法请详见我的另一篇博客:最短路径算法(上)——迪杰斯特拉(Dijikstra)算法
弗洛伊德(Floyd)算法是解决任意两点间的最短路径的一种算法,可以正确处理有向图或有向图或负权(但不可存在负权回路)的最短路径问题,同时也被用于计算有向图的传递闭包。
(一)算法思想:
Floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在)。
从任意节点i到任意节点j的最短路径不外乎2种可能,一是直接从i到j,二是从i经过若干个节点k到j。所以,我们假设Dis(i,j)为节点u到节点v的最短路径的距离,对于每一个节点k,我们检查Dis(i,k) + Dis(k,j) Dis(i,j)是否成立,如果成立,证明从i到k再到j的路径比i直接到j的路径短,我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j),这样一来,当我们遍历完所有节点k,Dis(i,j)中记录的便是i到j的最短路径的距离。
(二)算法过程
1)首先把初始化距离dist数组为图的邻接矩阵,路径数组path初始化为-1。其中对于邻接矩阵中的数首先初始化为正无穷,如果两个顶点存在边则初始化为权重
2)对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是就更新它。
状态转移方程为
如果 dist[k]+dist[k][j] dist[j]
则dist[j] = dist[k]+dist[k][j]
for(int k = 1 ; k this- Nv+1 ; k++){ //k代表中间顶点
for(int i = 1 ; i this- Nv+1 ; i++){//i代表起始顶点
for(int j = 1 ; j this- Nv+1 ; j++){//j代表终点
if(this- dist[k] + this- dist[k][j] this- dist[j]){
this- dist[j] = this- dist[k] + this- dist[k][j];
if(i == j this- dist[j] 0){//发现了负值圈
return false;
this- path[j] = k;
return true;
}
我们用如下图结构来演示Floyd算法:


全部代码为:
#include iostream
#include cstring
#include stack
#include queue
using namespace std;
const int MAX = 65535;
class Graph{
private:
int** G; //邻接矩阵
int** dist; //距离数组
int** path; //路径数组
int Nv; //顶点数
public:
//构造函数
Graph(int nv, int ne){
this- Nv = nv;
G = new int*[nv+1];
dist = new int*[nv+1];
path = new int*[nv+1];
for(int i = 0 ; i nv+1 ; i++){
G = new int[nv+1];
dist = new int[nv+1];
path = new int[nv+1];
memset(path,-1,sizeof(path[0][0])*(nv+1));
for(int j = 0 ; j nv+1 ; j++){
this- G[j] = this- dist[j] = MAX;
cout "请输入边与权重:" endl;
for(int i = 0 ; i ne ; i++){
int v1,v2,weight;
cin v1 v2 weight;
this- G[v1][v2] = this- G[v2][v1] = weight;
this- dist[v1][v2] = this- dist[v2][v1] = weight;
//Floyd算法(多源最短路径算法)
bool Floyd(){
for(int k = 1 ; k this- Nv+1 ; k++){ //k代表中间顶点
for(int i = 1 ; i this- Nv+1 ; i++){//i代表起始顶点
for(int j = 1 ; j this- Nv+1 ; j++){//j代表终点
if(this- dist[k] + this- dist[k][j] this- dist[j]){
this- dist[j] = this- dist[k] + this- dist[k][j];
if(i == j this- dist[j] 0){//发现了负值圈
return false;
this- path[j] = k;
return true;
//打印start顶点到end顶点的路径
void Print_Path(int start,int end){
stack int stack;
queue int queue;
int k = this- path[start][end]; //start与end之间的路径必须经过的顶点
int tmp = k; //临时保存k
if(k == -1){ //如果start与end之间没有中间结点
//打印start与end后结束函数
cout start "- " end endl;
return;
stack.push(k); //中间顶点入栈
//首先找到start与k之间的路径
//由于是从后往前找路径,故利用堆栈
while(this- path[start][k] != -1){
stack.push(this- path[start][k]);
k = this- path[start][k];
stack.push(start);
//然后找到k与end之间的路径
//由于是从前往后找路径,故用队列
while(this- path[tmp][end] != -1){
queue.push(this- path[tmp][end]);
tmp = this- path[tmp][end];
queue.push(end);
//打印路径
cout stack.top();
stack.pop();
while(!stack.empty()){
cout "- " stack.top();
stack.pop();
while(!queue.empty()){
cout "- " queue.front();
queue.pop();
cout endl;
void Print_Floyd(){
int i,j,k;
cout " length path" endl;
for(i = 1 ; i this- Nv+1 ; i++){
for(j = i+1 ; j this- Nv+1 ; j++){
cout i "- " j " ";
cout this- dist[j] " ";
this- Print_Path(i,j);
cout endl;
int main()
cout "请输入顶点数与边长数:" endl;
int nv,ne;
cin nv ne;
Graph graph(nv,ne);
if(graph.Floyd()){
cout "各个顶点的最短路径为:" endl;
graph.Print_Floyd();
return 0;
}
截图如下:

利用BP神经网络对语音数据进行分类
qq_30091945:
@angran12345:其实复杂不带哪去。毕竟有些东西是为了验证结果才加上去,并写成了注释。毕竟p...

序列交换
qq_26894901:
你不用纠结啦 他那个貌似有问题 这个错误的例子是所有的数都不相同 也算一种 我看到过一个 是交换之...

利用BP神经网络对语音数据进行分类
qq_30091945:
@major_zhang:不考研,计算机发展图太快,以不变应万变,在工作中去学习。

神奇数
qq_30091945:
@qq_28618031:题目已经说明了范围,就不存在越界的情况。况且我这个也是AC了的。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
温馨提示:
1、在论坛里发表的文章仅代表作者本人的观点,与本网站立场无关。
2、论坛的所有内容都不保证其准确性,有效性,时间性。阅读本站内容因误导等因素而造成的损失本站不承担连带责任。
3、若因线路及非本站所能控制范围的故障导致暂停服务期间造成的一切不便与损失,论坛不负任何责任。
4,本网站内容均摘自其他网站,如涉及侵权定当第一时间删除
5、如侵犯您的权益请联系936144721@qq.com



上一篇:在吾悦的世界里,没有复制粘贴!
下一篇:基层党支部委员会委员选票、书记和副书记选票
转载请说明出处,本文地址:http://bbs.imicun.com/thread-15464310-1-1.html
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表