弗洛伊德算法采用图的带权邻接矩阵存储结构。
算法基本思想
假设求顶点Vi到Vj的最短路径。弗洛伊德算法依次找从Vi到Vj，中间经过结点序号不大于0的最短路径，不大于1的最短路径，…直到中间顶点序号不大于n-1的最短路径，从中选取最小值，即为Vi到Vj的最短路径。
算法具体描述
若从Vi到Vj有弧，则从Vi到Vj存在一条长度为弧上权值（arcs[i][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）[i][j]=arcs[i][j]
D（k）[i][j]=Min{ D（k-1）[i][j], D（k-1）[i][k]+D（k-1）[k][j]} 0≤k≤n-1
上述公式中，D（1）[i][j]是从 Vi到Vj的中间顶点序号不大于 k的最短路径长度；D（n-1）[i][j]是从Vi到Vj的最短路径长度。
打开IDE
我们创建一个工程
类声名如下
#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_)类实现如下
#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[i][j]=0;}
else {//初始化无(有)向有权图
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(i==j) GA[i][j]=0;
else GA[i][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[i][j]=GA[j][i]=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[i][j]=GA[j][i]=w;}
}
else if(k1!=0 && k2==0) { //建立有向无权图
cout<<"输入"<<e<<"条有向无权边的起点和终点序号!"<<endl;
for(k=1; k<=e; k++) {
cin>>i>>j;
Check(n,i,j);
GA[i][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[i][j]=w;}}
numE=e;
cout<<"创建后的邻接矩阵:\n";
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
cout<<setw(4)<<GA[i][j];
cout<<endl;}
}
//从初始点vi出发深度优先搜索由邻接矩阵表示的图
void AdjMatrix::dfsMatrix(bool*& visited,int i,int n,int k2)
{cout<<g[i]<<':'<<i<<" ";
visited[i]=true; //标记vi已被访问过
for(int j=0; j<n; j++) //依次搜索vi的每个邻接点
if(k2==0)
{if(i!=j&&GA[i][j]!=0&&!visited[j])
dfsMatrix(visited,j,n,k2);}
else
if(i!=j&&GA[i][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]<<':'<<i<<" ";
//标记初始点vi已访问过
visited[i]=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[i][j]!=0) {
edgenode* p=new edgenode;
p->adjvex=j;
p->next=GL[i];GL[i]=p;
cout<<'('<<i<<','<<p->adjvex<<") ";}
cout<<endl;}}
else {
for(i=0;i<n;i++){
for(j=0;j<n;j++)
if(GA[i][j]!=0 && GA[i][j]!=MaxValue) {
edgenode* p=new edgenode;
p->adjvex=j;p->weight=GA[i][j];
p->next=GL[i];GL[i]=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[i][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[i][j]!=0 && GA[i][j]!=MaxValue)
if(k==i&&m<n)
{g[m]='A'+m;size++;
cout<<g[m]<<'('<<i<<','<<j<<','<<GA[i][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[i];
}
//取弧<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[i]=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[i][j]>0&&GA[i][j]<MaxValue)
{GA[i][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[i]=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[i]=false;
for(int i=0;i<NumV();i++)
if(!vis[i]) 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[i]=false;
for(int i=0;i<NumV();i++)
if(!vis[i]) bfsMatrix(vis,i,n,k2);
delete []vis;
}
代码调用如下
#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[i][j]=G.GetWeight(i,j);
if(i!=j&&dist[i][j]!=MaxValue) path[i][j]=i;
else
if(i==j) path[i][j]=0;
else path[i][j]=-1;
}
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{if(dist[i][j]>(dist[i][k]+dist[k][j]))
{dist[i][j]=dist[i][k]+dist[k][j];
path[i][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[i][j]<<endl;
cout<<"从顶点"<<g.GetValue(i)
<<"到其他各顶点的最短路径的前一顶点为:\n";
for(j=0;j<m;j++)
if(path[i][j]!=-1)
cout<<"到顶点"<<g.GetValue(j)<<"的前一顶点为:"
<<g.GetValue(path[i][j])<<endl;
}
cin.get();cin.get();
}效果如下
代码下载如下
http://download.csdn.net/detail/yincheng01/4789961