算法基础 - 多源点最短路径(Floyd算法)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法基础 - 多源点最短路径(Floyd算法),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2068字,纯文字阅读大概需要3分钟。
内容图文
![算法基础 - 多源点最短路径(Floyd算法)](/upload/InfoBanner/zyjiaocheng/1094/cbe092257a044231ad9465075d27bb09.jpg)
Floyd算法
Floyd算法又称为插点法,是一种用于寻找给定的加权图中多源点之间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
思路
路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
从图的带权邻接矩阵
A=[a(i,j)] n×n
开始,递归地进行n
次更新,即由矩阵D(0)=A
,按一个公式,构造出矩阵D(1)
;又用同样地公式由D(1)构造出D(2);……;最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度,称D(n)为图的距离矩阵,同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
引用自:百度百科
采用松弛技术(松弛操作),对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3)
;
状态转移方程
其状态转移方程如下:
map[i,j]:=min{map[i,k]+map[k,j],map[i,j]};
map[i,j]
表示i到j的最短距离,K
是穷举i,j
的断点,map[n,n]
初值应该为0,或者按照题目意思来做。
当然,如果这条路没有通的话,还必须特殊处理,比如没有map[i,k]
这条路。
其实就是枚举第三个点,看是否能出现
1->3->2
的距离比1->2
的短
复杂度
时间复杂度: O(N^3);
空间复杂度:O(N^2);
伪代码
For k:=1 to n
For i:=1 to n
For j:=1 to n
IfD[i,j]>D[i,k]+D[k,j] Then
D[i,j]:=D[i,k]+D[k,j];
代码实现
//
// main.cpp
// HiHocoder
//
// Created by Alps on 16/5/9.
// Copyright ? 2016年 chen. All rights reserved.
//
#include <iostream>
#include <cstring>
#include <string>
using
namespace
std;
longlong dist[102][102]; //表示最大节点数是101个longlong minNum(longlong a, longlong b){
if(a == -1) return b;
return a < b ? a : b;
}
void floyd(longlong dist[][102], int N){
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
for(int k = 1; k <= N; k++){
if(dist[j][i] == -1 || dist[i][k] == -1){
continue;//如果没路径别走
}
dist[j][k] = minNum(dist[j][k], dist[j][i]+dist[i][k]);
}
}
}
}
int main(){
int N,M;
while(cin>>N>>M){
for(int i = 0; i <= N; i++){
for(int j = 0; j <= N; j++){
dist[i][j] = -1; //初始化为-1 表示无穷远if(i == j){
dist[i][j] = 0;
}
}
}
int x, y, d;
for(int i = 0; i < M; i++){
cin>>x>>y>>d;
dist[x][y] = minNum(dist[x][y], d);
dist[y][x] = dist[x][y];//无向图,如果是有向图去掉这个路径
}
floyd(dist, N);
for(int i = 1; i <= N; i++){ //输出整个矩阵for(int j = 1; j<= N; j++){
cout<<dist[i][j]<<" ";
}
cout<<endl;
}
}
return0;
}
原文:http://blog.csdn.net/alps1992/article/details/51369975
内容总结
以上是互联网集市为您收集整理的算法基础 - 多源点最短路径(Floyd算法)全部内容,希望文章能够帮你解决算法基础 - 多源点最短路径(Floyd算法)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。