锐客网

  1. 首页 > 睿知 > it技术 > >

弗洛伊德算法代码java 弗洛伊德算法代码实现

IT技术出题

遗传算法求最短路径#includestdio.h
#includeiostream
#includestring.h
#includemalloc.h
#includestdlib.h
#includestring
using namespace std;
#define OVERFLOW -2
#define OK 1
#define ERROR 0
#define INFINITY 200//最大值
#define MAX_VERTEX_NUM 20//最大顶点个数
typedef char VertexType;//定义为char类型
//以下是全局变量,用于保存弗洛伊德算法的路径和长度
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径长度
int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];//记录最短路径标记
//以下是全局变量,用于保存迪杰斯特拉算法的路径和长度
int Distance[MAX_VERTEX_NUM];
VertexType former[MAX_VERTEX_NUM];//终点的前一个顶点
bool final[MAX_VERTEX_NUM];//记录顶点是否在V-S中
typedef struct ArcCell
{
int adj;//顶点关系类型
intweight;//该弧相关信息的指针,在此记录为权值
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM];//顶点向量
AdjMatrix arcs;//邻接矩阵
int vexnum;//顶点数
int arcnum;//弧数
}MGraph;
void InitialMGraph(MGraph G)//初始化
{
G.arcnum=G.vexnum=0;//初始化边数跟顶点数都为零
for(int i=0;iMAX_VERTEX_NUM;i++)
for(int j=0;jMAX_VERTEX_NUM;j++)
{
if(i==j)
G.arcs[i][j].weight=0;
else
G.arcs[i][j].weight=INFINITY;//初始化为200,以200认为是无穷大
}
}
void InsertVex(MGraph G,VertexType v)//插入顶点
{
if(G.vexnum=MAX_VERTEX_NUM)
G.vexs[G.vexnum++]=v;
}
void InsertArc(MGraph G,VertexType v1,VertexType v2)//插入边
{
int m,n;
G.arcnum++;
for(int k=0;kG.vexnum;k++)
{
if(G.vexs[k]==v1)
m=k;
if(G.vexs[k]==v2)
n=k;
}
//插入
ArcCell A;
cout"请输入权值:";
cinA.weight;
G.arcs[m][n].weight=A.weight;
}
//迪杰斯特拉最短路径,假设始点就存储在数组中的第一个
void ShortestPath_DIJ(MGraph G,int v0)
{
//初始化距离
for(int v=0;vG.vexnum;++v)
【弗洛伊德算法代码java 弗洛伊德算法代码实现】 {
final[v]=false;
Distance[v]=G.arcs[v0][v].weight;
if(Distance[v]INFINITYDistance[v]!=0)
{
former[v]=G.vexs[v0];
}
else
former[v]='#';
}
final[v0]=true;
former[v0]=G.vexs[v0];
for(int i=1;iG.vexnum;++i)//剩余的G.vexnum-1个顶点
{
int w;
int min=INFINITY;
int v=-1;
for(w=0;wG.vexnum;++w)
{
if(!final[w]Distance[w]min)
{
v=w;
min=Distance[w];
}
}
if(v!=-1)
{
final[v]=true;//将离顶点V0最近的顶点v加入S集合中
for(w=0;wG.vexnum;++w)//更新当前的最短路径及距离
{
if(!final[w](min+G.arcs[v][w].weightDistance[w])G.arcs[v][w].weightINFINITY)
{
Distance[w]=min+G.arcs[v][w].weight;
former[w]=G.vexs[v];
}
}
}
}
}
//输出迪杰斯特拉中的最短路径
void output_ShortestPath_DIJ(MGraph G,int v0)
{
int i;
for(i=1;iG.vexnum;i++)
{
coutG.vexs[v0]"-"G.vexs[i]":";
if(Distance[i]!=INFINITY)
{
cout"最短路径长度为:"Distance[i]" 最短路径的前一个顶点为:"former[i];
coutendl;
}
else
cout"此两顶点之间不存在路径"endl;
}
}
//弗洛伊德最短路径
void shortestPath_FLOYD(MGraph G)
{
for(int v=0;vG.vexnum;++v)
{
for(int w=0;wG.vexnum;++w)
{
D[v][w]=G.arcs[v][w].weight;
for (int k=0;k G.vexnum;k++)
P[v][w][k]=-1;

推荐阅读


上一篇：工业无线网络怎么用路由器，迷你路由器怎么设置无线网络

下一篇：word怎么设置段后距，word中如何设置段后间距