三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 开发 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 编程 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> C++ -> floyd算法学习笔记 -> 正文阅读
 

[C++]floyd算法学习笔记

floyd算法学习笔记 算法思路
路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。从图的带权邻接矩阵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来记录两点间的最短路径。
状态转移方程
其状态转移方程如下: 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,从任意一条单边路径开始。所有两点之间的距离是边的权,如果两点之间没有边相连,则权为无穷大。
2,对于每一对顶点 u 和 v,看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来,如果从Vi到Vj有路可达,则G[i,j]=d,d表示该路的长度;否则G[i,j]=无穷大。定义一个矩阵D用来记录所插入点的信息,D[i,j]表示从Vi到Vj需要经过的点,初始化D[i,j]=j。把各个顶点插入图中,比较插点后的距离与原来的距离,G[i,j] = min( G[i,j], G[i,k]+G[k,j] ),如果G[i,j]的值变小,则D[i,j]=k。在G中包含有两点之间最短道路的信息,而在D中则包含了最短通路径的信息。
时间复杂度与空间复杂度
时间复杂度:因为核心算法是采用松弛法的三个for循环,因此时间复杂度为O(n^3)
空间复杂度:整个算法空间消耗是一个n*n的矩阵,因此其空间复杂度为O(n^2)
C++代码
// floyd.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include"iostream"
#include"fstream"
#define maxlen 20
#define maximum 100
using namespace std;
typedef struct graph
{
 int vertex;
 int edge;
 int matrix[maxlen][maxlen];
};
int _tmain(int argc, _TCHAR* argv[])
{
 ofstream outwrite;
 outwrite.open("h.txt",ios::app|ios::out);
 outwrite<<"welcome to the graph world!\n";
 outwrite<<"the initial matrix is:\n";
 int vertexnumber;
 int edgenumber;
 int beginning,ending,weight;
 int mindistance[maxlen][maxlen];
 int interval[maxlen][maxlen];
 graph floydgraph;
 cout<<"welcome to the graph world!"<<endl;
 cout<<"input the number of the vertex: ";
 cin>>vertexnumber;
 cout<<"input the number of the edge: ";
 cin>>edgenumber;
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   floydgraph.matrix[i][j]=maximum;
  }
 }
 for (int i = 0; i <edgenumber; i++)
 {
  cout<<"please input the beginning index: ";
  cin>>beginning;
  cout<<"please input the ending index: ";
  cin>>ending;
  cout<<"please input the distance of the two dot: ";
  cin>>weight;
  floydgraph.matrix[beginning][ending]=weight;
 }
 for (int i = 0; i <vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   mindistance[i][j]=floydgraph.matrix[i][j];
   outwrite<<floydgraph.matrix[i][j]<<"\t";
   interval[i][j]=-1;
  }
  outwrite<<"\n";
 }
 for (int k = 0; k <vertexnumber; k++)
 {
  for (int i = 0; i < vertexnumber; i++)
  {
   for (int j = 0; j < vertexnumber; j++)
   {
    if(mindistance[i][j]>mindistance[i][k]+mindistance[k][j])
    {
     mindistance[i][j]=mindistance[i][k]+mindistance[k][j];
     interval[i][j]=k;
    }
   }
  }
 }
 outwrite<<"\n"<<"after the floyd transition, the matrix is: "<<"\n";
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   cout<<"the mindistance between "<<i<<"  and  "<<j <<" is: ";
   cout<<mindistance[i][j]<<endl;
   cout<<"the two points pass through the point: "<<interval[i][j];
   cout<<endl;
   outwrite<<mindistance[i][j]<<"\t";
  }
  outwrite<<"\n";
 }
 outwrite<<"\n";
 outwrite<<"the points between the beginning point and the ending point is:"<<"\n";
 for (int i = 0; i < vertexnumber; i++)
 {
  for (int j = 0; j < vertexnumber; j++)
  {
   outwrite<<interval[i][j]<<"\t";
  }
  outwrite<<"\n";
 }
 outwrite.close();
 getchar();
 getchar();
 getchar();
 return 0;
}
  C++ 最新文章
关于poin与references
019:别叫,这个大整数已经很简化了!
c++智能指针详解
BZOJ1269: [AHOI2006]文本编辑器editor
洛谷P3835 【模板】可持久化平衡树
洛谷P2925 [USACO08DEC]干草出售Hay For Sa
威尔逊定理
c++ Windows Socket实现最简单的C/S网络通信
洛谷P1306 斐波那契公约数
C++中引用传递与指针传递区别
上一篇文章      下一篇文章      查看所有文章
加:2016-10-30 16:43:28  更:2017-05-15 13:39:11 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年5日历
2018-5-24 4:24:20
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库