滴水逆向联盟
标题: VC++2012编程演练数据结构《30》弗洛伊德算法 [打印本页]
作者: 大灰狼 时间: 2014-8-19 08:53
标题: VC++2012编程演练数据结构《30》弗洛伊德算法
弗洛伊德算法是基于动态规划的求解有负权图的单源最短路的一种较高效的算法。时间复杂度：O(n^3)空间复杂度：O(n^2)
弗洛伊德算法采用图的带权邻接矩阵存储结构。
算法基本思想
假设求顶点Vi到Vj的最短路径。弗洛伊德算法依次找从Vi到Vj，中间经过结点序号不大于0的最短路径，不大于1的最短路径，…直到中间顶点序号不大于n-1的最短路径，从中选取最小值，即为Vi到Vj的最短路径。
算法具体描述
若从Vi到Vj有弧，则从Vi到Vj存在一条长度为弧上权值（arcs[j] ）的路径，该路径不一定是最短路径，尚需进行n次试探。
首先考虑从Vi到Vj经过中间顶点V0的路径（Vi，V0，Vj）是否存在，也就是判断弧（Vi，V0）和（V0，Vj）是否存在。若存在，则比较（Vi，Vj）和（Vi，V0，Vj）的路径长度取较短的为从Vi到Vj的中间顶点序号不大于0的最短路径。
在此路径上再增加一个顶点V1，也就是说，如果（Vi，…V1）和（V1，…Vj）分别是当前找到的中间顶点序号不大于0的最短路径，那么，（Vi，…V1，…Vj）就有可能是从Vi到Vj的中间顶点序号不大于1的最短路径。将它和已经得到的从Vi到Vj中间顶点序号不大于0的最短路径相比较，从中选出最短的作为从Vi到Vj中间顶点序号不大于1的最短路径。
然后，再增加一个顶点V2继续进行这个试探过程。
一般情况下，若（Vi，…Vk）和（Vk，…Vj）分别是从Vi到Vk和从Vk到Vj的中间顶点序号不大于k-1的最短路径，则将（Vi，…，Vk，…Vj）和已经得到的从Vi到Vj的中间顶点序号不大于k-1的最短路径相比较，其长度最短者即为从Vi到Vj的中间顶点序号不大于k的最短路径。
经过n次比较之后，最后求得的便是从Vi到Vj的最短路径。
按此方法可同时求得各对顶点之间的最短路径。
现定义一个n阶方阵序列
D（-1），D（0），D（1），…，D（k），…，D（n-1）
其中
D（-1）[j]=arcs[j]
D（k）[j]=Min{ D（k-1）[j], D（k-1）[k]+D（k-1）[k][j]} 0≤k≤n-1
上述公式中，D（1）[j]是从 Vi到Vj的中间顶点序号不大于 k的最短路径长度；D（n-1）[j]是从Vi到Vj的最短路径长度。
打开IDE
我们创建一个工程
类声名如下
[cpp] view plaincopy
- #if !defined(AFX_GRAPH_H__5D7EB16D_8ECD_46B8_9C6C_20723A4F93C1__INCLUDED_)
- #define AFX_GRAPH_H__5D7EB16D_8ECD_46B8_9C6C_20723A4F93C1__INCLUDED_
-
- #if _MSC_VER > 1000
- #pragma once
- #endif // _MSC_VER > 1000
-
- //图的相关数据类型的定义graph.h
- //最多顶点数
- const int MaxV=10;
- //最大权值
- const int MaxValue=99;
- //定义邻接表中的边结点类型
- struct edgenode {
- int adjvex; //邻接点域
- int weight; //权值域
- edgenode* next;//指向下一个边结点的链域
- };
- //定义邻接表类型
- typedef edgenode** adjlist;
- //邻接矩阵类定义
- class AdjMatrix
- {private:
- char g[MaxV];//顶点信息数组
- int size;//当前顶点数
- int GA[MaxV][MaxV];//定义邻接矩阵GA
- int numE;//当前边数
- public:
- //构造函数,初始化图的邻接矩阵
- AdjMatrix(int n,int k2);
- //判断图空否
- bool GraphEmpty() {return size==0;}
- //取当前顶点数
- int NumV() {return size;}
- //取当前边数
- int NumEdges() {return numE;}
- //取顶点i的值
- char GetValue(const int i);
- //取弧<v1,v2>的权
- int GetWeight(const int v1,const int v2);
- //在位置pos处插入顶点V
- void InsertV(const char &V,int pos);
- //插入弧<v1,v2>,权为weight
- void InsertEdge(const int v1,const int v2,int weight);
- //删除顶点i与顶点i相关的所有边
- char DeleteVE(const int i);
- //删除弧<v1,v2>
- void DeleteEdge(const int v1,const int v2);
- //建立图的邻接矩阵
- void CreateMatrix(int n, int k1,int k2);
- //k1为0则无向否则为有向,k2为0则无权否则为有权
- //从初始点vi出发深度优先搜索由邻接矩阵表示的图
- void dfsMatrix(bool*& visited,int i,int n,int k2);
- //从初始点vi出发广度优先搜索由邻接矩阵表示的图
- void bfsMatrix(bool*& visited,int i,int n,int k2);
- //由图的邻接矩阵得到图的邻接表
- void graphChange(adjlist &GL,int n,int k2);
- //检查输入的边序号是否越界,若越界则重输
- void Check(int n,int& i,int& j);
- //由图的邻接矩阵建立图
- void Creatgraph(int n,int k2);
- //对非连通图进行深度优先搜索
- void dfsMatrix(int n,int k2);
- //对非连通图进行广度优先搜索
- void bfsMatrix(int n,int k2);
- };
-
- #endif // !defined(AFX_GRAPH_H__5D7EB16D_8ECD_46B8_9C6C_20723A4F93C1__INCLUDED_)
类实现如下
[cpp] view plaincopy
- #include "stdafx.h"
- #include "graph.h"
-
- //图的相关运算的实现graph.cpp
- #include"graph.h"
- //构造函数,初始化图的邻接矩阵
- AdjMatrix::AdjMatrix(int n,int k2)
- {int i,j;
- if(k2==0){//初始化无(有)向无权图
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- GA[j]=0;}
- else {//初始化无(有)向有权图
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- if(i==j) GA[j]=0;
- else GA[j]=MaxValue;}
- size=numE=0;
- }
- //建立图的邻接矩阵
- void AdjMatrix::CreateMatrix(int n,int k1,int k2)
- //k1为0则无向否则为有向,k2为0则无权否则为有权
- {int i,j,k,e,w;
- cout<<"输入图的总边数:";
- cin>>e;
- if(k1==0 && k2==0) { //建立无向无权图
- cout<<"输入"<<e<<"条无向无权边的起点和终点序号!"<<endl;
- for(k=1; k<=e; k++) {
- cin>>i>>j;
- Check(n,i,j);
- GA[j]=GA[j]=1;}
- }
- else if(k1==0 && k2!=0) { //建立无向有权图
- cout<<"输入"<<e<<"条无向带权边的起点和终点序号及权值!"<<endl;
- for(k=1; k<=e; k++) {
- cin>>i>>j>>w;
- Check(n,i,j);
- GA[j]=GA[j]=w;}
- }
- else if(k1!=0 && k2==0) { //建立有向无权图
- cout<<"输入"<<e<<"条有向无权边的起点和终点序号!"<<endl;
- for(k=1; k<=e; k++) {
- cin>>i>>j;
- Check(n,i,j);
- GA[j]=1;}
- }
- else if(k1!=0 && k2!=0) { //建立有向有权图
- cout<<"输入"<<e<<"条有向有权边的起点和终点序号及权值!"<<endl;
- for(k=1; k<=e; k++) {
- cin>>i>>j>>w;
- Check(n,i,j);
- GA[j]=w;}}
- numE=e;
- cout<<"创建后的邻接矩阵:\n";
- for(i=0;i<n;i++)
- {for(j=0;j<n;j++)
- cout<<setw(4)<<GA[j];
- cout<<endl;}
- }
- //从初始点vi出发深度优先搜索由邻接矩阵表示的图
- void AdjMatrix::dfsMatrix(bool*& visited,int i,int n,int k2)
- {cout<<g<<':'<<i<<" ";
- visited=true; //标记vi已被访问过
- for(int j=0; j<n; j++) //依次搜索vi的每个邻接点
- if(k2==0)
- {if(i!=j&&GA[j]!=0&&!visited[j])
- dfsMatrix(visited,j,n,k2);}
- else
- if(i!=j&&GA[j]!=MaxValue&&!visited[j])
- dfsMatrix(visited,j,n,k2);
- }
- //从初始点vi出发广度优先搜索由邻接矩阵表示的图
- void AdjMatrix::bfsMatrix(bool*& visited,int i,int n,int k2)
- {const int MaxLength=30;
- //定义一个队列q,其元素类型应为整型
- int q[MaxLength]={0};
- //定义队首和队尾指针
- int front=0,rear=0;
- //访问初始点vi
- cout<<g<<':'<<i<<" ";
- //标记初始点vi已访问过
- visited=true;
- //将已访问过的初始点序号i入队
- q[++rear]=i;
- //当队列非空时进行循环处理
- while(front!=rear) {
- //删除队首元素,第一次执行时k的值为i
- front=(front+1)%MaxLength;
- int k=q[front];
- //依次搜索vk的每一个可能的邻接点
- for(int j=0;j<n;j++)
- if(k2==0)
- {if(k!=j&&GA[k][j]!=0&&!visited[j])
- {//访问一个未被访问过的邻接点vj
- cout<<g[j]<<':'<<j<<" ";
- visited[j]=true; //标记vj已访问过
- rear=(rear+1)%MaxLength;//顶点序号j入队
- q[rear]=j;
- }
- }
- else
- if(k!=j&&GA[k][j]!=MaxValue&&!visited[j])
- {//访问一个未被访问过的邻接点vj
- cout<<g[j]<<':'<<j<<" ";
- visited[j]=true; //标记vj已访问过
- rear=(rear+1)%MaxLength;//顶点序号j入队
- q[rear]=j;
- }
- }}
- //检查输入的边序号是否越界,若越界则重输
- void AdjMatrix::Check(int n,int& i,int& j)
- {while(1) {
- if(i<0||i>=n||j<0||j>=n)
- cout<<"输入有误,请重输!";
- else return;
- cin>>i>>j;
- }
- }
- //由图的邻接矩阵得到图的邻接表
- void AdjMatrix::graphChange(adjlist &GL,int n,int k2)
- {int i,j;
- if(k2==0)
- {for(i=0;i<n;i++){
- for(j=0;j<n;j++)
- if(GA[j]!=0) {
- edgenode* p=new edgenode;
- p->adjvex=j;
- p->next=GL;GL=p;
- cout<<'('<<i<<','<<p->adjvex<<") ";}
- cout<<endl;}}
- else {
- for(i=0;i<n;i++){
- for(j=0;j<n;j++)
- if(GA[j]!=0 && GA[j]!=MaxValue) {
- edgenode* p=new edgenode;
- p->adjvex=j;p->weight=GA[j];
- p->next=GL;GL=p;
- cout<<'('<<i<<','<<p->adjvex<<','<<p->weight<<") ";}
- cout<<endl;}
- }}
- //由图的邻接矩阵建立图
- void AdjMatrix::Creatgraph(int n,int k2)
- {int i,j,k,m=0;
- if(k2==0)
- {for(i=0;i<n;i++){
- k=i;
- for(j=0;j<n;j++)
- if(GA[j]!=0)
- if(k==i&&m<n)
- {g[m]='A'+m;size++;
- cout<<g[m]<<'('<<i<<','<<j<<") ";
- m++;
- }
- }
- cout<<endl;}
- else {
- for(i=0;i<n;i++){
- k=i;
- for(j=0;j<n;j++)
- if(GA[j]!=0 && GA[j]!=MaxValue)
- if(k==i&&m<n)
- {g[m]='A'+m;size++;
- cout<<g[m]<<'('<<i<<','<<j<<','<<GA[j]<<") ";
- m++;
- }
- }
- cout<<endl;}
- g[n]='\0';
- }
- //取顶点i的值
- char AdjMatrix::GetValue(const int i)
- {if(i<0||i>size)
- {cerr<<"参数i越界!\n";exit(1);}
- return g;
- }
- //取弧<v1,v2>的权
- int AdjMatrix::GetWeight(const int v1,const int v2)
- {if(v1<0||v1>size||v2<0||v2>size)
- {cerr<<"参数v1或v2越界!\n";exit(1);}
- return GA[v1][v2];
- }
- //在位置pos处插入顶点V
- void AdjMatrix::InsertV(const char &V,int pos)
- {int i;
- if(size==MaxV)
- {cerr<<"表已满,无法插入!\n";exit(1);}
- if(pos<0||pos>size)
- {cerr<<"参数pos越界!\n";exit(1);}
- for(i=size;i>pos;i--) g=g[i-1];
- g[pos]=V;
- size++;
- }
- //插入弧<v1,v2>,权为weight
- void AdjMatrix::InsertEdge(const int v1,const int v2,int weight)
- {if(v1<0||v1>size||v2<0||v2>size)
- {cerr<<"参数v1或v2越界!\n";exit(1);}
- GA[v1][v2]=weight;
- numE++;
- }
- //删除顶点v与顶点v相关的所有边
- char AdjMatrix::DeleteVE(const int v)
- {for(int i=0;i<size;i++)
- for(int j=0;j<size;j++)
- if((i==v||j==v)&&GA[j]>0&&GA[j]<MaxValue)
- {GA[j]=MaxValue;
- numE--;}
- if(size==0)
- {cerr<<"表已空,无元素可删!\n";exit(1);}
- if(v<0||v>size-1)
- {cerr<<"参数v越界!\n";exit(1);}
- char temp=g[v];
- for(int i=v;i<size-1;i++) g=g[i+1];
- size--;
- g[size]='\0';
- return temp;
- }
- //删除弧<v1,v2>
- void AdjMatrix::DeleteEdge(const int v1,const int v2)
- {if(v1<0||v1>size||v2<0||v2>size||v1==v2)
- {cerr<<"参数v1或v2出错!\n";exit(1);}
- GA[v1][v2]=MaxValue;
- numE--;
- }
- //对非连通图进行深度优先搜索
- void AdjMatrix::dfsMatrix(int n,int k2)
- {bool *vis=new bool[NumV()];
- for(int i=0;i<NumV();i++) vis=false;
- for(int i=0;i<NumV();i++)
- if(!vis) dfsMatrix(vis,i,n,k2);
- delete []vis;
- }
- //对非连通图进行广度优先搜索
- void AdjMatrix::bfsMatrix(int n,int k2)
- {bool *vis=new bool[NumV()];
- for(int i=0;i<NumV();i++) vis=false;
- for(int i=0;i<NumV();i++)
- if(!vis) bfsMatrix(vis,i,n,k2);
- delete []vis;
- }
代码调用如下
[cpp] view plaincopy
- #include "stdafx.h"
- #include "graph.h"
-
- void Floyd(AdjMatrix &G,int dist[6][6],int path[6][6])
- //求图G中每对顶点之间的最短距离dist和最短路径的顶点序号path
- {int i,j,k;
- int n=G.NumV();
- for(i=0;i<n;i++)//初始化
- for(j=0;j<n;j++)
- {dist[j]=G.GetWeight(i,j);
- if(i!=j&&dist[j]!=MaxValue) path[j]=i;
- else
- if(i==j) path[j]=0;
- else path[j]=-1;
- }
- for(k=0;k<n;k++)
- for(i=0;i<n;i++)
- for(j=0;j<n;j++)
- {if(dist[j]>(dist[k]+dist[k][j]))
- {dist[j]=dist[k]+dist[k][j];
- path[j]=path[k][j];
- }}}
-
-
-
-
- //弗洛伊德算法测试
- void main()
- {cout<<"运行结果:\n";
- int n=6,k1=1,k2=1,i,j;
- AdjMatrix g(n,k2);
- g.CreateMatrix(n,k1,k2);
- cout<<"输出邻接矩阵相应图的顶点:\n";
- g.Creatgraph(n,k2);
-
- int m=g.NumV();
- int dist[6][6],path[6][6];
- Floyd(g,dist,path);
- for(i=0;i<m;i++)
- {cout<<"从顶点"<<g.GetValue(i)
- <<"到其他各顶点的最短距离为:\n";
- for(j=0;j<m;j++)
- cout<<"到顶点"<<g.GetValue(j)
- <<"的最短距离为:"<<dist[j]<<endl;
- cout<<"从顶点"<<g.GetValue(i)
- <<"到其他各顶点的最短路径的前一顶点为:\n";
- for(j=0;j<m;j++)
- if(path[j]!=-1)
- cout<<"到顶点"<<g.GetValue(j)<<"的前一顶点为:"
- <<g.GetValue(path[j])<<endl;
- }
- cin.get();cin.get();
- }
效果如下
| 欢迎光临 滴水逆向联盟 (http://dtdebug.com/) |
Powered by Discuz! X3.2 |