问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501

最短路径代码

发布网友 发布时间：2022-04-30 10:24

我来回答

共2个回答

热心网友 时间：2022-06-21 03:21

#include<iostream.h>

// 定义 状态代码 及 数据类型
#define NULL 0
#define OK 1
#define ERROR 0
#define INFINITY 255
#define MAX_VERTEX_NUM 20

typedef int Status;
typedef int ElemType;

// ----------------------- 队列结构 -------------------------

// 节点存储结构
typedef struct QNode{
ElemType data;
struct QNode *next;
}QNode,*QueuePtr;

// 队列
typedef struct{
QueuePtr front;
QueuePtr rear;
}LinkQueue;

// 初始化队列
Status InitQueue(LinkQueue &Q){
Q.front=Q.rear=new QNode;
if(!Q.front)
return ERROR;
Q.front->next=NULL;
return OK;
}

// 入队
Status EnQueue(LinkQueue &Q,ElemType e){
QueuePtr p=NULL;
p=new QNode;
if(!p)
return ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return OK;
}

// 出队
Status DeQueue(LinkQueue &Q,ElemType &e){
QueuePtr p=NULL;
if(Q.front==Q.rear)
return ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p) // 注意当出队后为空队的情况
Q.rear=Q.front;
delete p;
return OK;
}

// 判断是否为空队列
Status EmptyQueue(LinkQueue &Q){
return Q.front==Q.rear?true:false;
}

// 复制队列(copy Q1 to Q2)
Status CopyQueue(LinkQueue &Q1,LinkQueue &Q2){
int e;
QueuePtr p;
while(!EmptyQueue(Q2)){ // clean Q2
DeQueue(Q2,e);
} // copy one by one
p=Q1.front->next;
while(p){
e=p->data;
p=p->next;
EnQueue(Q2,e);
}
return OK;
}

// ---------------------- 图的结构：邻接矩阵（有向网） --------------------------//

// 邻接矩阵元素
typedef struct ArcCell{
int adj; // arc value: >0, INFINITY: no link
char *info;
}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

// 图的结构
typedef struct{
char vexs[MAX_VERTEX_NUM][5]; // 顶点数组
AdjMatrix arcs; // 邻接矩阵
int vexnum; // 图当前的顶点数
int arcnum; // 图当前边的个数
}MGraph;

// 建立邻接图（key=1为有向网，key=0为无向网）
Status CreateUDN(MGraph &G,int vexnum,int edgenum,char *names,char *edges,int key){
int i,j,k,value;
// 输入当前图的顶点数，边个数
G.vexnum=vexnum;
G.arcnum=edgenum;
// 各个顶点数据
for(i=0;i<G.vexnum;++i){
for(j=0;j<4;j++){
G.vexs[i][j]=*names;
names++;
}
G.vexs[i][4]='\0';
}
// 初始化邻接矩阵（全为INFINITY）
for(i=0;i<MAX_VERTEX_NUM;++i){
for(j=0;j<MAX_VERTEX_NUM;++j){
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;

}
}
// 建立邻接矩阵每条边的数值
for(k=0;k<G.arcnum;++k){
i=int(*edges)-48;
edges++;
j=int(*edges)-48;
edges++;
value=(int(*edges)-48)*10;
edges++;
value+=int(*edges)-48;
edges++;
G.arcs[i][j].adj=value;
if(!key){
G.arcs[j][i].adj=value;
}
}
return OK;
}

// 打印出邻接矩阵
void PrintGraph(MGraph &G){
int i,j;
cout<<"\n//--------------- PrintMatrix -----------------//\n\n ";
for(i=0;i<G.vexnum;++i){
cout<<G.vexs[i]<<" ";
}
cout<<endl;
for(i=0;i<G.vexnum;++i){
cout<<"\n\n"<<G.vexs[i]<<" ";
for(j=0;j<G.vexnum;++j){
if(G.arcs[i][j].adj==INFINITY)
cout<<" / ";
else
cout<<" "<<G.arcs[i][j].adj<<" ";
}
}
cout<<"\n\n//--------------- PrintMatrix -----------------//\n";
}

// ---------------------- 求源点v0到各点的最短路径 --------------------------//

void ShortestPath(MGraph &G,int v0){
int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
// 建立队列数组，用以依次储存最短的路径
LinkQueue Q[MAX_VERTEX_NUM];
// 初始化数组
for(i=0;i<G.vexnum;++i){
InitQueue(Q[i]);
D[i]=G.arcs[v0][i].adj;
final[i]=false;
}
final[v0]=true;
// 一个一个循环找出最短距离（共vexnum－1个）
for(i=1;i<G.vexnum;++i){
min=INFINITY;
// 扫描找出非final集中最小的D[]
for(w=0;w<G.vexnum;++w){
if(!final[w] && D[w]<min){
v=w;
min=D[w];
}
}
final[v]=true;
// 更新各D[]数据
for(w=0;w<G.vexnum;++w){
if(!final[w] && G.arcs[v][w].adj+min<D[w]){
D[w]=G.arcs[v][w].adj+min;
CopyQueue(Q[v],Q[w]);
EnQueue(Q[w],v);
}
}
}
// 打印出结果
cout<<"//--------------- ShortestPath -----------------//\n\n";
cout<<" 出发地->目的地\t最短距离\t详细路径\n\n";
for(i=0;i<G.vexnum;i++){
if(D[i]!=INFINITY){
cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\t"<<D[i]<<" \t\t";
cout<<G.vexs[v0];
while(!EmptyQueue(Q[i])){
DeQueue(Q[i],v);
cout<<" -> "<<G.vexs[v];
}
cout<<" -> "<<G.vexs[i]<<endl;
}else{
cout<<" "<<G.vexs[v0]<<" -> "<<G.vexs[i]<<"\t\tNo path!\n";

}
}
cout<<"\n//--------------- ShortestPath -----------------//\n";
}

void PrintCity(char *names,int vexnum){
int i,j;
cout<<"列表：\n\n";
for(i=0;i<vexnum;++i){
cout<<" "<<i<<"-";
for(j=0;j<4;j++){
cout<<*names;
names++;
}
cout<<" ";
}
cout<<"\n请选择出发地点 >";
}

void main(){
MGraph G;

// 图的结构数据
char *edges,*names;
int vexnum,arcnum,city,kind;
vexnum=6;
arcnum=10;
names="A1 A2 A3 A4 A5 A6";
edges="0103030505071205150623082403430152085407";

do{
PrintCity(names,vexnum);
cin>>city;
cout<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－无向图矩阵 3－有向图矩阵\n4－选择地点 5－退出\n\n请选择操作 >";
do{
cin>>kind;
if(kind>=0 && kind <=3){
CreateUDN(G,vexnum,arcnum,names,edges,kind%2);
switch(kind/2){
case 0:ShortestPath(G,city);
break;
case 1:PrintGraph(G);
break;
}
}
cout<<"\n\n操作：\n0－无向图列表 1－有向图列表\n2－无向图矩阵 3－有向图矩阵\n4－选择地点 5－退出\n\n请选择操作 >";
}
while(kind<4);
}
while(kind<5);
}

热心网友 时间：2022-06-21 03:21

#include<iostream.h>
//
定义
状态代码
及
数据类型
#define
NULL
0
#define
OK
1
#define
ERROR
0
#define
INFINITY
255
#define
MAX_VERTEX_NUM
20
typedef
int
Status;
typedef
int
ElemType;
//
-----------------------
队列结构
-------------------------
//
节点存储结构
typedef
struct
QNode{
ElemType
data;
struct
QNode
*next;
}QNode,*QueuePtr;
//
队列
typedef
struct{
QueuePtr
front;
QueuePtr
rear;
}LinkQueue;
//
初始化队列
Status
InitQueue(LinkQueue
&Q){
Q.front=Q.rear=new
QNode;
if(!Q.front)
return
ERROR;
Q.front->next=NULL;
return
OK;
}
//
入队
Status
EnQueue(LinkQueue
&Q,ElemType
e){
QueuePtr
p=NULL;
p=new
QNode;
if(!p)
return
ERROR;
p->data=e;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
return
OK;
}
//
出队
Status
DeQueue(LinkQueue
&Q,ElemType
&e){
QueuePtr
p=NULL;
if(Q.front==Q.rear)
return
ERROR;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
//
注意当出队后为空队的情况
Q.rear=Q.front;
delete
p;
return
OK;
}
//
判断是否为空队列
Status
EmptyQueue(LinkQueue
&Q){
return
Q.front==Q.rear?true:false;
}
//
复制队列(copy
Q1
to
Q2)
Status
CopyQueue(LinkQueue
&Q1,LinkQueue
&Q2){
int
e;
QueuePtr
p;
while(!EmptyQueue(Q2)){
//
clean
Q2
DeQueue(Q2,e);
}
//
copy
one
by
one
p=Q1.front->next;
while(p){
e=p->data;
p=p->next;
EnQueue(Q2,e);
}
return
OK;
}
//
----------------------
图的结构:邻接矩阵(有向网)
--------------------------//
//
邻接矩阵元素
typedef
struct
ArcCell{
int
adj;
//
arc
value:
>0,
INFINITY:
no
link
char
*info;
}AcrCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
//
图的结构
typedef
struct{
char
vexs[MAX_VERTEX_NUM][5];
//
顶点数组
AdjMatrix
arcs;
//
邻接矩阵
int
vexnum;
//
图当前的顶点数
int
arcnum;
//
图当前边的个数
}MGraph;
//
建立邻接图(key=1为有向网，key=0为无向网)
Status
CreateUDN(MGraph
&G,int
vexnum,int
edgenum,char
*names,char
*edges,int
key){
int
i,j,k,value;
//
输入当前图的顶点数，边个数
G.vexnum=vexnum;
G.arcnum=edgenum;
//
各个顶点数据
for(i=0;i<G.vexnum;++i){
for(j=0;j<4;j++){
G.vexs[i][j]=*names;
names++;
}
G.vexs[i][4]='\0';
}
//
初始化邻接矩阵(全为INFINITY)
for(i=0;i<MAX_VERTEX_NUM;++i){
for(j=0;j<MAX_VERTEX_NUM;++j){
G.arcs[i][j].adj=INFINITY;
G.arcs[i][j].info=NULL;
}
}
//
建立邻接矩阵每条边的数值
for(k=0;k<G.arcnum;++k){
i=int(*edges)-48;
edges++;
j=int(*edges)-48;
edges++;
value=(int(*edges)-48)*10;
edges++;
value+=int(*edges)-48;
edges++;
G.arcs[i][j].adj=value;
if(!key){
G.arcs[j][i].adj=value;
}
}
return
OK;
}
//
打印出邻接矩阵
void
PrintGraph(MGraph
&G){
int
i,j;
cout<<"\n//---------------
PrintMatrix
-----------------//\n\n
";
for(i=0;i<G.vexnum;++i){
cout<<G.vexs[i]<<"
";
}
cout<<endl;
for(i=0;i<G.vexnum;++i){
cout<<"\n\n"<<G.vexs[i]<<"
";
for(j=0;j<G.vexnum;++j){
if(G.arcs[i][j].adj==INFINITY)
cout<<"
/
";
else
cout<<"
"<<G.arcs[i][j].adj<<"
";
}
}
cout<<"\n\n//---------------
PrintMatrix
-----------------//\n";
}
//
----------------------
求源点v0到各点的最短路径
--------------------------//
void
ShortestPath(MGraph
&G,int
v0){
int
D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
//
建立队列数组，用以依次储存最短的路径
LinkQueue
Q[MAX_VERTEX_NUM];
//
初始化数组
for(i=0;i<G.vexnum;++i){
InitQueue(Q[i]);
D[i]=G.arcs[v0][i].adj;
final[i]=false;
}
final[v0]=true;
//
一个一个循环找出最短距离(共vexnum-1个)
for(i=1;i<G.vexnum;++i){
min=INFINITY;
//
扫描找出非final集中最小的D[]
for(w=0;w<G.vexnum;++w){
if(!final[w]
&&
D[w]<min){
v=w;
min=D[w];
}
}
final[v]=true;
//
更新各D[]数据
for(w=0;w<G.vexnum;++w){
if(!final[w]
&&
G.arcs[v][w].adj+min<D[w]){
D[w]=G.arcs[v][w].adj+min;
CopyQueue(Q[v],Q[w]);
EnQueue(Q[w],v);
}
}
}
//
打印出结果
cout<<"//---------------
ShortestPath
-----------------//\n\n";
cout<<"
出发地->目的地\t最短距离\t详细路径\n\n";
for(i=0;i<G.vexnum;i++){
if(D[i]!=INFINITY){
cout<<"
"<<G.vexs[v0]<<"
->
"<<G.vexs[i]<<"\t\t"<<D[i]<<"
\t\t";
cout<<G.vexs[v0];
while(!EmptyQueue(Q[i])){
DeQueue(Q[i],v);
cout<<"
->
"<<G.vexs[v];
}
cout<<"
->
"<<G.vexs[i]<<endl;
}else{
cout<<"
"<<G.vexs[v0]<<"
->
"<<G.vexs[i]<<"\t\tNo
path!\n";
}
}
cout<<"\n//---------------
ShortestPath
-----------------//\n";
}
void
PrintCity(char
*names,int
vexnum){
int
i,j;
cout<<"列表:\n\n";
for(i=0;i<vexnum;++i){
cout<<"
"<<i<<"-";
for(j=0;j<4;j++){
cout<<*names;
names++;
}
cout<<"
";
}
cout<<"\n请选择出发地点
>";
}
void
main(){
MGraph
G;
//
图的结构数据
char
*edges,*names;
int
vexnum,arcnum,city,kind;
vexnum=6;
arcnum=10;
names="A1
A2
A3
A4
A5
A6";
edges="0103030505071205150623082403430152085407";
do{
PrintCity(names,vexnum);
cin>>city;
cout<<"\n\n操作:\n0-无向图列表
1-有向图列表\n2-无向图矩阵
3-有向图矩阵\n4-选择地点
5-退出\n\n请选择操作
>";
do{
cin>>kind;
if(kind>=0
&&
kind
<=3){
CreateUDN(G,vexnum,arcnum,names,edges,kind%2);
switch(kind/2){
case
0:ShortestPath(G,city);
break;
case
1:PrintGraph(G);
break;
}
}
cout<<"\n\n操作:\n0-无向图列表
1-有向图列表\n2-无向图矩阵
3-有向图矩阵\n4-选择地点
5-退出\n\n请选择操作
>";
}
while(kind<4);
}
while(kind<5);
}
声明声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com
如果只有铬黑T试剂,能否测定钙离子,如何测定? 金银花茶的做法窍门 怎样制作金银花茶 怎么快速取消订单 有关"听"开头的成语 王卡看腾讯视频不显示免流 大王卡腾讯视频不显示免流 谁给推荐几部国产的好看的、卟幼稚的、新鲜的动画片 好看的、不幼稚的国产动画片有哪些? 太早的不要,要连续动画片 上传速度慢是什么原因? rag是什么意思 蓝宝石是怎样形成的? 如何去构建邻接图变成许多维数约简问题的关键 什么是邻接图 宝石需要多少年才能形成 高中化学必修2的1至20号原子的电子式 宝石怎么来? 高中化学必修二预习 宝石矿物的形成类型 俄罗斯一处海滩遍地是宝石,那这些宝石是怎么形成的? 宝石是什么生成的 宝石是怎样形成? 宝石是怎么形成的 2015年河南省教师资格证考试有哪些报名条件呢? 河南省教师资格证通过率是多少分 梦见老公和我一起睡捏我肚子疼的叫不出声 如何拦截微信对sqllite数据库做插入的信息 黑豆黑米黑芝麻打豆浆是晚上喝可以吗 黑豆,红豆,黑米红米红腰豆,可以一起打豆浆吗 黑豆,黑米,黑芝麻,可以混合用豆浆机打成糊糊吃吗,功效一样吗 红宝石是怎样形成的 区域生长的区域生长 matlab 以坐标画圆 地形图的检查、清绘、拼接与整饰 网格 为什么三角形图元最多有三个邻接图元?而不是更多 图的邻接表转换邻接矩阵算法 小学四年级上册语文第三单元小木偶的故事思维导图怎么画 cocos2dx 3.0 游戏存档的实现 求苏州自考网? 苏州自学考试哪里报名? 苏州市自考考点在什么地方?怎么查? 离职的理由千千万,你会因为哪些原因离职? 被解雇或离职往往是因为什么原因 你会因为什么而选择离职? 一般离职都是因为哪些原因? 你会因为什么原因而辞职? 巴以冲突到底和美国有什么关系? 最近的巴以冲突打起来是为什么打起来的？因为什么？很多人都说是美国搞得？这和美国有什么关系？不明白 美国为什么不承认巴勒斯坦的国家地位? 巴勒斯坦为什么会讨厌美国？是什么历史事件导致的？经济，*和社会因素呢？
懂视 51dongshi.com 版权所有
Copyright © 2019-2024