#include
#include
using namespace std ;

#define MUNum 20
#define INFINITY 32767
#define Myprintf cout << "\n\t+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-\n" << endl

typedef struct PlaneGraph
{
int PathLength ;
char Pathname[20] ;
}PlaneGraph,PG[MUNum][MUNum] ;

typedef struct
{
char name[20] ;
int num ;
}infor ;

typedef struct
{
infor vexs[MUNum] ;
PG arcs ;
int vexnum ,arcnum ;
}AMGraph ;

void InitGraph(AMGraph &G)
{
int i ,j ;
cout << "\t请输入校园地点的数量、校园小径的个数:" ;
cin >> G.vexnum >> G.arcnum ;//点 边
Myprintf ;

``````for(i=0 ;i<G.vexnum ;i++)
G.vexs[i].num = i ;//为点进行编号

cout << " 输入编号为(0-" << i << ")的校园地点的名称:\n\n" ;//店名称
for(i=0 ;i<G.vexnum ;i++)
{
cout << "\t" ;
cin  >> G.vexs[i].name ;
}

cout << endl ;
Myprintf ;

for(i=0 ;i<G.vexnum ;i++)
for(j=0 ;j<G.vexnum ;j++)
{
G.arcs[i][j].PathLength = INFINITY ;
strcpy(G.arcs[i][j].Pathname,"null");
}

//输入路径信息
int v1,v2,w ;
char wn[20] ;
cout << "输入校园小径首尾地点编号、小径长度及小径名称\n\t(以-1 -1 -1 -1)结束输入:\n\t" << endl ;
cin  >> v1 >> v2 >> w >> wn ;
while(v1!=-1 && v2!=-1 && w!=-1 && strcmp(wn,"-1")!=0)
{
cout << "\t" ;
G.arcs[v1][v2].PathLength = w ;
strcpy(G.arcs[v1][v2].Pathname,wn);
G.arcs[v2][v1].PathLength = w ;
strcpy(G.arcs[v2][v1].Pathname,wn);
cin >> v1 >> v2 >> w >> wn ;
}

Myprintf ;
``````

}

//Floyd
void ShortestPath(AMGraph G)
{
int v,u,i,j,w,k,flag=1;
int p[MUNum][MUNum][MUNum],D[MUNum][MUNum];
for(v=0 ; v for(w=0 ;w {
D[v][w] = G.arcs[v][w].PathLength;
for(u=0;u p[v][w][u] = 0 ;//
if(D[v][w] p[v][w][v] = p[v][w][w] = 1;//
}
for(u=0 ;u for(v=0 ;v for(w=0 ;w if(D[v][u]+D[u][w] {
D[v][w] = D[v][u]+D[u][w];
for(i=0;i p[v][w][i] = p[v][u][i] || p[u][w][i];//
}
while(flag)
{
cout cin >> k >> j ;
if(k=G.vexnum || j=G.vexnum )
{
cout << "该地点不存在!请重新输入!" << endl ;
Myprintf ;
}
else if(k == j )
{
cout << "始点和终点相同!请重新输入!" << endl ;

Myprintf ;
}
else
flag = 0 ;
}

``````    //输出信息
int L[MUNum];
L[0] = k;
int l = 1 ;

cout << "\t总路线长:" << D[k][j] << endl ;

cout << G.vexs[k].name ;
for(u=0 ;u<G.vexnum ;u++)
if(p[k][j][u] && k!=u && j!=u)
{
cout << " ——> " << G.vexs[u].name ;
L[l] = u ;
l++ ;
}

cout << " ——> " << G.vexs[j].name ;
L[l] = j ;
cout << endl ;

cout << "\t路线:" ;
for(u=0 ;u<l ;u++)
{
cout << G.arcs[L[u]] [L[u+1]].Pathname ;
if(u != l-1)
cout << " ——> " ;
}
cout << endl ;
Myprintf ;
``````

}

int main()
{
cout << "\n----------------------------------校园导航----------------------------------" << endl << endl ;
AMGraph G ;
InitGraph(G) ;
char k[10] ;
strcpy(k,"Yes");
while(strcmp(k,"Yes")==0)
{
ShortestPath(G);
cout << "请问是否继续?Yes or No?" << endl ;
cin >> k ;
if(strcmp(k,"Yes") != 0 )
cout << "\n----------------------------------停止查询----------------------------------" << endl ;
}
return 0 ;
}

10 10

0 1 10 逸夫路
1 3 15 敬文路
4 3 70 达夫路
1 2 20 朝阳路
3 7 77 富康路
4 5 12 人民路
5 6 19 孚玉路
6 7 56 龙门路
8 9 73 纬七路
8 7 8 九江路
-1 -1 -1 -1

2个回答

http://blog.csdn.net/hackerain/article/details/6055946
#define MAX_VERTEX_NUM 20
#define MAX 1000000000
typedef struct
{
std::string vexs[MAX_VERTEX_NUM];
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];......

----------------------你好，人类，我是来自CSDN星球的问答机器人小C，以上是依据我对问题的理解给出的答案，如果解决了你的问题，望采纳。

floyd算法求任意两点最短路径，为什么输出的邻接矩阵总不正确
#include <iostream> using namespace std; #define MaxSize 100 #define INF 9999 class MGraph { public: void CreatMGraph(MGraph &); void ppath(int path[][100],int i,int j); void DisPath(int dist[][100],int path[][100],int n); void Floyd(MGraph G); void print(MGraph G); private: int edge[MaxSize][MaxSize]; char vertex[MaxSize]; int n,e; }; void MGraph::ppath(int path[][MaxSize],int i,int j) { int k; k=path[i][j]; if (k==-1) return; ppath(path,i,k); printf("%d,",k); ppath(path,k,j); } void MGraph::DisPath(int dist[][MaxSize],int path[][MaxSize],int n) { int i,j; for(i=0;i<n;i++) { for(j=0;j<n;j++) { cout<<"请输入需要查找的顶点："; cin>>i>>j; if (dist[i][j]!=INF && i!=j) { printf(" 从%d到%d路径为:",i,j); printf("%d,",i); ppath(path,i,j); printf("%d",j); printf("\t最短路径长度为:%d\n",dist[i][j]); } } } } void MGraph::Floyd(MGraph G) { int i,j,k,dist[MaxSize][MaxSize]; int n=G.n; int path[MaxSize][MaxSize]; for(i=0;i<n;i++) for(j=0;j<n;j++) { dist[i][j]=G.edge[i][j]; 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][k]+dist[k][j]<dist[i][j]) { dist[i][j]=dist[i][k]+dist[k][j]; path[i][j]=k; } DisPath(dist,path,n); } void MGraph::CreatMGraph(MGraph &G) { int i,j,k,w; int kind; int count=0; cout<<"请输入顶点数和边数:"; cin >> G.n >> G.e; cout<<"请输入边依附的顶点和权值:"<<endl; for(i=0;i<G.n;i++) { for(int j=0; j<G.n;j++) { G.edge[i][j] =INF; if(i==j) { G.edge[i][j]=0; } } } for(int k=0; k<G.e;k++) { cin >> i >> j >> w; G.edge[i][j] = w; if(kind==2) G.edge[j][i]=w; count++; } } void MGraph::print(MGraph G) { cout << "图的邻接矩阵为：" << endl; int i = 0; //打印行的标签 int j = 0; //打印列的标签 while (i!=G.n) { j= 0; while (j!=G.n) { if (G.edge[i][j] ==INF) cout << "∞" << " "; else cout << G.edge[i][j] << " "; j++; } cout << endl; i++; } } int main() { cout << "输入图的种类：1代表有向图，2代表无向图" << endl; int kind; cin >> kind; while (1) { if (kind == 1 || kind == 2) { break; } else { cout << "输入的图的种类编号不合法，请重新输入：1代表有向图，2代表无向图" << endl; cin >> kind; } } MGraph g; g.CreatMGraph(g); g. print(g); g.Floyd(g); printf("\n"); return 0; }

4．交通咨询系统 任务：设计一个简易交通咨询系统，能让旅客咨询从人一个城市到另一个城市之间的最短路径。 功能要求： （1）建立交通网络图的存储结构，并输出； （2）求单源最短路径（Dijkstra算法），并输出； （3）求任一对城市之间的最短路径，并输出。 第三个，无论我输入哪两个，都会显示无路径，这是为什么呢？求解 （ps:因为代码不是自己写的，所以想问问怎么解决）谢谢啦 ``` #include<stdio.h> #include<stdlib.h> #define MVNum 100 #define Maxint 0 typedef char VertexType; typedef int Adjmatrix; int D1[MVNum],P1[MVNum]; int D[MVNum][MVNum],P[MVNum][MVNum]; typedef enum {FALSE,TRUE}boolean; typedef struct{ VertexType vexs[MVNum] ; Adjmatrix arcs[MVNum][MVNum]; }MGraph; /*采用邻接矩阵表示法构造有向图G,n,e表示图的当前顶点数和边数*/ void CreateMGraph(MGraph *G,int n,int e) { int i,j,k,w; for(i=1;i<=n;i++) G->vexs[i]=(char)i; for(i=1;i<=n;i++) for(j=1;j<=n;j++) G->arcs[i][j]=Maxint; printf("输入%d条边的i,j及w: \n",e); for(k=1;k<=e;k++) { scanf("%d,%d,%d",&i,&j,&w); G->arcs[i][j]=G->arcs[j][i]=w; } printf("有向图的储存结构构建完毕！\n"); } /* 用Dijkstra算法求有向图G的v1顶点到其他顶点v的最短路经p[v] 以及其权D[v] 设G是有向向图的邻接矩阵，若 边<i,j> 不存在，则G[i][j]=Maxint S[v]为真当且仅当v属于S,即已求得从v1到v的最短路经 */ void Dijkstra(MGraph G,int v1,int n) { int D2[MVNum],P2[MVNum]; int v,i,w,min; boolean S[MVNum]; for(v=1;v<=n;v++) { S[v]=FALSE; D2[v]=G.arcs[v1][v]; if(D2[v]<Maxint) P2[v]=v1; else P2[v]=0; }//end_for D2[v1]=0; S[v1]=TRUE; //开始循环，每次求得v1到某个v顶点的最短路经，并将v加到S集总 for(i=2;i<n;i++) { min=Maxint; for(w=1;w<=n;w++) if(!S[w] && D2[w]<min) { v=w; min=D2[w]; } S[v]=TRUE; for(w=1;w<=n;w++) if(!S[w] && (D2[v]+G.arcs[v][w]<D2[w])) { //修改D2[w]和P2[w],w属于V-S D2[w]=D2[v]+G.arcs[v][w]; P2[w]=v; }//end_if }//end_for printf("路经长度 路经\n"); for(i=1;i<=n;i++) { printf("%5d",D2[i]); printf("%5d",i); v=P2[i]; while(v!=0) { printf("<-%d",v); v=P2[v]; } printf("\n"); } } /*弗洛伊德算法*/ void Floyd(MGraph G,int n) { int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(G.arcs[i][j]!=Maxint) P[i][j]=j; else P[i][j]=0; D[i][j]=G.arcs[i][j]; } //做k次迭代，每次迭代均试图将顶点k扩充到当前求得的从i到j的最短路经Pij上 for(k=1;k<=n;k++) { for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(D[i][k]+D[k][j]<D[i][j]) { D[i][j]=D[i][k]+D[k][j]; //修改长度 P[i][j]=P[i][k]; } } } } /*主函数*/ int main(void) { MGraph G; int n,e,v,w,k; int i,j; int xz=1; printf("输入图中顶点的个数和边数n,e:"); scanf("%d,%d",&n,&e); CreateMGraph(&G,n,e); printf("输出交通网络图的存储结构:\n"); for(i=0;i<n;i++) { for(j=0;j<n;j++) printf("%d\t",G.arcs[i][j]); printf("\n"); } while(xz!=0) { printf("************求城市之间的最短路经************\n"); printf("============================================\n"); printf("1.求一个城市到所有城市的最短路经\n"); printf("2.求任意的两个城市之间的最短路经\n"); printf("============================================\n"); printf(" 请选择： 1 或 2 . 选择 0 退出 ："); scanf("%d",&xz); if(xz==2) { Floyd(G,n); printf("请输入源点（或称起点）和终点： V , W : "); scanf("%d,%d",&v,&w); k=P[v][w]; if(k==0) printf("顶点%d到%d无路经!\n",v,w); else { printf("从顶点%d到%d的最短路经是：%d",v,w,v); while(k!=w) { printf("->%d",k); k=P[k][w]; } printf("->%d\n",w); printf(" 路经长度：%d\n",D[v][w]); } } else if(xz==1) { printf("求单源路经，输入源点 v : "); scanf("%d",&v); Dijkstra(G,v,n); } } printf("结束求最短路经，再见！\n\n"); } ``` ![图片说明](https://img-ask.csdn.net/upload/201912/31/1577783926_868731.png)

``` #include<iostream> #include<iomanip> using namespace std; #define MAXINT 10000 /*无穷大*/ #define MVNUM 40 #define MAX 40 typedef struct { char *name; int num; char *introduction; }INFORMATION; typedef struct ACCESS { int length; }ACCESS,LENGTHA[MVNUM][MVNUM]; typedef struct { INFORMATION VEXS[MVNUM]; LENGTHA ARCS;// Maybe error int VEXNUM,ARCNUM; }AMGRAPH; AMGRAPH A;//全局变量 AMGRAPH CreatGraph() //初始化 { AMGRAPH G; int i, j; G.VEXNUM = 12; //14个顶点 G.ARCNUM = 16; //14条弧 for (i = 0; i<G.VEXNUM; i++) G.VEXS[i].num = i; //第i个景点的编号为i G.VEXS[0].name="26栋宿舍"; G.VEXS[1].name="二饭"; G.VEXS[2].name="泳池"; G.VEXS[3].name="网球场"; G.VEXS[4].name="沙地"; G.VEXS[5].name="旧场"; G.VEXS[6].name="新场"; G.VEXS[7].name="明德楼"; G.VEXS[8].name="图书馆"; G.VEXS[9].name="弘毅楼"; G.VEXS[10].name="天佑楼"; G.VEXS[11].name="艺悦楼"; G.VEXS[0].introduction="26栋宿舍位于学子路西侧，是计算机学院学生所住宿舍，万通超市上方。"; G.VEXS[1].introduction="第二学生饭堂位于学子路东侧，是学生好评最多的食堂。"; G.VEXS[2].introduction="北理工泳池位于学校后山半山腰上，对学生及社会人士都开放。"; G.VEXS[3].introduction="网球场位于学校东门附近，有4个场地供学生打网球。"; G.VEXS[4].introduction="沙地位于网球场西侧，以往学生在此举办各种活动，是一处聚会场地。"; G.VEXS[5].introduction="旧场位于网球场北侧，是北理珠最早的篮球场。"; G.VEXS[6].introduction="新场位于沙地西侧，是较新的篮球场。"; G.VEXS[7].introduction="明德楼位于学校中部，在夺命坡上方，是主要教学楼之一。"; G.VEXS[8].introduction="图书馆位于学校北门一侧，集图书馆、办公室、酒店于一体。"; G.VEXS[9].introduction="弘毅楼位于学校新大门对面，是主要教学楼之一。"; G.VEXS[10].introduction="天佑楼位于弘毅楼西侧，是航空学院的主教学楼。"; G.VEXS[11].introduction="艺悦楼位于天佑楼西侧，是设计与艺术学院的主教学楼。"; for (i = 0; i<G.VEXNUM; i++) for (j = 0; j<G.VEXNUM; j++) G.ARCS[i][j].length = MAXINT; G.ARCS[0][1].length=20; G.ARCS[0][2].length=100; G.ARCS[0][3].length=280; G.ARCS[1][3].length=280; G.ARCS[1][4].length=110; G.ARCS[1][7].length=210; G.ARCS[2][7].length=130; G.ARCS[1][9].length=280; G.ARCS[3][4].length=20; G.ARCS[3][5].length=5; G.ARCS[4][6].length=5; G.ARCS[5][8].length=35; G.ARCS[6][8].length=50; G.ARCS[7][9].length=80; G.ARCS[8][9].length=200; G.ARCS[9][10].length=40; G.ARCS[10][11].length=20; for (i=0;i<G.VEXNUM;i++) for (j=0;j<G.VEXNUM;j++) G.ARCS[j][i].length = G.ARCS[i][j].length; //无向网 return G; } void SHORTESTPATH_DIJ(AMGRAPH *G) {//DIJ算法，计算最短路径 int V,min,i,j,w,k=0,V0,f=1,t; int D[32],PATH[32][32]; bool S[32]; while (f) { cout<<"请输入一个起始景点编号:"; cin>>V0; //输入一个值赋给V0 if (V0<0 || V0>G->VEXNUM) { cout<<"景点编号不存在!请重新输入景点编号:"; cin>>V0; } if (V0 >=0 && V0<G->VEXNUM) f=0; } for(V=0;V<G->VEXNUM;V++) { S[V]=false; D[V]=G->ARCS[V0][V].length; for(w=0;w<G->VEXNUM;w++) { PATH[V][w]=0; } if(D[V]<MAXINT) { PATH[V][V0]=1; PATH[V][V]=1; } } D[V0]=0; S[V0]=true; for(i=1;i<G->VEXNUM;i++) { min=MAXINT; for(w=0;w<G->VEXNUM;w++) { if(!S[w]&&D[w]<min) { V=w; min=D[w]; } } S[V]=true; for(w=0;w<G->VEXNUM;w++) { if(!S[w] && (min+G->ARCS[V][w].length<D[w])) { D[w]=min+G->ARCS[V][w].length; for(j=0;j<G->VEXNUM;j++) PATH[w][j]=PATH[V][j]; PATH[w][w]=1; } } } for(V=0;V<G->VEXNUM;V++) { t=0; if(V0!=V) printf("%s",G->VEXS[V0].name); for(w=0;w<G->VEXNUM;w++) { if(PATH[V][w]!=0 && w!=V0) { printf("-%s",G->VEXS[w].name); if(w==5||w==6) { t=1; } } k++; } if(V0!=V&&(V0==5||V0==6||t==1)) { cout<<"\t此路段部分需步行！"; t=0; } if(k>G->VEXNUM-1 && V0!=V) printf("\t路程：%dm\n\n",D[V]); } } void SHORTESTPATH_FLOYD(AMGRAPH G) {//FLOYD算法计算各对顶点之间的最短路径 int D[32][32],PATH[32][32]; int i,j,k; for(i=0;i<G.VEXNUM;i++) for(j=0;j<G.VEXNUM;i++) { D[i][j]=G.ARCS[i][j].length; if(D[i][j]<MAXINT) PATH[i][j]=i; else PATH[i][j]=-1; } for(k=0;k<G.VEXNUM;k++) for(i=0;i<G.VEXNUM;i++) for(j=0;j<G.VEXNUM;j++) { if(D[i][k]+D[k][j]<D[i][j]) { D[i][j]=D[i][k]+D[k][j]; PATH[i][j]=PATH[k][j]; } } } void printjuzhen(AMGRAPH G) { int i,j,W=0; cout<<"图的邻接矩阵:"<<endl; for(i=0;i<G.VEXNUM;i++) { for(j=0;j<G.VEXNUM;j++) { if(G.ARCS[i][j].length==MAXINT) { cout<<setw(6)<<"∞"; } else cout<<setw(6)<<G.ARCS[i][j].length; W++; if(W%G.VEXNUM==0) cout<<endl; } } } void main() { A=CreatGraph(); SHORTESTPATH_DIJ(&A); printjuzhen(A); } ``` ![图片说明](https://img-ask.csdn.net/upload/201612/24/1482560926_949494.jpg) ![图片说明](https://img-ask.csdn.net/upload/201612/24/1482560938_648604.jpg) 请问怎么可以正确地打印最近的路，而不是按照地点的数字顺序打印出错误的线路。

``` #include <stdio.h> #include <math.h> #define MAXSIZE 100 #define Infinity 10001 int G[MAXSIZE][MAXSIZE],Nv,Ne,Distance,x[MAXSIZE],y[MAXSIZE],path[MAXSIZE][MAXSIZE],FirstPoint[MAXSIZE],count=0,count_2=0,Destination[MAXSIZE],D[MAXSIZE][MAXSIZE]; int GetDistance(int Xa,int Ya,int Xb,int Yb) { return (int)pow((pow(Xa-Xb,2)+pow(Ya-Yb,2)),0.5); } void PrintPath(int i,int j) { } void BuildGraph() { int i,j; scanf("%d %d", &Nv,&Distance); if(Distance+7.5>=50) { printf("1\n"); return ; } for (i = 0; i<Nv; i++) { scanf("%d %d",&x[i],&y[i]); if(GetDistance(x[i],y[i],0,0)<=7.5+Distance) { FirstPoint[count]=i; count++; } if(!(abs(x[i])<50-Distance&&abs(y[i])<50-Distance)) { Destination[count_2]=i; count_2++; } } for (i = 0; i<Nv; i++) { for (j = 0; j<Nv; j++) { if(GetDistance(x[i],y[i],x[j],y[j])<=Distance&&i!=j) { G[i][j]=1; G[j][i]=1; } else if(i==j) { G[i][j]=0; } else { G[i][j]=Infinity; G[j][i]=Infinity; } } } } void FindPath() { int i,j,k,MinDist=Infinity,Temp_i,Temp_j; for(i=0;i<Nv;i++) { for(j=0;j<Nv;j++) { D[i][j]=G[i][j]; path[i][j]=-1; } } for(k=0;k<Nv;k++) { for(i=0;i<Nv;i++) { for(j=0;j<Nv;j++) { if(D[i][k]+D[k][j]<D[i][j]) { D[i][j]=D[i][k]+D[k][j]; path[i][j]=k; } } } } for(i=0;i<count;i++) { for(j=0;j<count_2;j++) { if(D[FirstPoint[i]][Destination[j]]<MinDist) { MinDist=D[FirstPoint[i]][Destination[j]]; Temp_i=FirstPoint[i]; Temp_j=Destination[j]; } } } if(MinDist==Infinity) { printf("0\n"); } else { printf("%d\n",D[Temp_i][Temp_j]+2); PrintPath(Temp_i,Temp_j); } } int main() { BuildGraph(); FindPath(); return 0; } ``` 请问如何用递归的方法写出PrintPath这个函数？ 测试数据 输入 17 15 10 -21 10 21 -40 10 30 -50 20 40 35 10 0 -10 -25 22 40 -40 -30 30 -10 22 0 11 25 21 25 10 10 10 10 35 -30 10 输出 4 0 11 10 21 10 35 原题链接：https://pta.patest.cn/pta/test/1342/exam/4/question/23159 代码写的比较乱 不好意思

## **题目** ---------------------------------------------------------------------------------------------------------------------------------------------------------------------- Description Floyd-Warshall算法是求一个图中任意两点之间的最短路径长度的算法。 给出一个有向图，请计算图中任意两个顶点之间的最短路径，及其长度。 Input 单测试用例。 第一行是该有向图的 顶点数n ( 0 < n < 500 )（注：图有n个顶点，首个顶点的编号是0。 ） 第二行是该有向图的 边数e ( 0 < e < n×n ) 接下来e行，每行三个整数 i 、j 和 k，表示 顶点i 到顶点j 有一条弧，长度为k。 ( 0 ≤ i, j < n ) （注：输入数据中不含 自环 。） 接下来一个正整数Q，表示有Q个询问。 接下来Q行，每行两个非负整数u和v，表示询问 顶点u 到 顶点v 的最短路长度，以及该最短路径是怎么走的。 Output 对每个询问输出三行。 第一行是一个整数，表示顶点u到顶点v的最短路长度。如果不可达，输出INF ，且不用输出第二行。如果路径长度为0，也不用输出第二行。 第二行是若干个整数，每个整数后面跟一个空格，表示顶点u 到顶点v 的最短路的顶点序列。 第三行是一个空行，仅起分隔作用。 Sample Input 3 5 0 1 4 0 2 11 1 0 6 1 2 2 2 0 3 3 0 2 0 1 1 0 Sample Output 6 0 1 2 4 0 1 5 1 2 0 Hint 样例如下图所示 1397_1.png 注意：本题是special judge，但validator没有写得很完美。你的代码输出时如果没有间隔的空行，PE会判为WA ------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以下是本人的代码 #include<stdio.h> #include<stdlib.h> #define MAX 505 typedef struct { int edges[MAX][MAX]; int n,e; }MGraph; MGraph G; int D[MAX][MAX],path[MAX][MAX]; int inf=99999999; void Path(int u,int v) { int k; k=path[u][v]; if(k==-1) return ; Path(u,k); printf("%d ",k); Path(k,v); } void Dispath(int u,int v) { if(D[u][v]==inf||D[u][v]==0) { printf("INF\n"); } else { printf("%d\n",D[u][v]); printf("%d ",u); Path(u,v); printf("%d\n",v); } } void Floyd(MGraph G) { int Q,u,v; int i,j,k; for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) { D[i][j]=G.edges[i][j]; path[i][j]=-1; } } /*for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",D[i][j]); printf("\n"); } printf("\n");*/ for(k=0;k<G.n;k++) { for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) if(D[i][k]<inf&&D[k][j]<inf&&D[i][j]>(D[i][k]+D[k][j])) { D[i][j]=D[i][k]+D[k][j]; //printf("%d ",D[i][j]); path[i][j]=k; }} } /*for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",D[i][j]); printf("\n"); } printf("\n"); for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",path[i][j]); printf("\n"); } system("pause");*/ scanf("%d",&Q); for(i=0;i<Q;i++) { scanf("%d %d",&u,&v); Dispath(u,v); printf("\n"); } } int main() { int i,j,k,t; scanf("%d",&G.n); scanf("%d",&G.e); for(i=0;i<G.n;i++)/////////////ÁÚ½Ó¾ØÕó³õÊ¼»¯ for(j=0;j<G.n;j++) { if(i==j) G.edges[i][j]=0; else G.edges[i][j]=inf; //printf("%d ",G.edges[i][j]); } //printf("\n"); //printf("%d",G.e); //printf("%d\n",INF); for(t=0;t<G.e;t++) { //system("pause"); scanf("%d %d %d",&i,&j,&k); G.edges[i][j]=k; } /*for(i=0;i<G.n;i++) { for(j=0;j<G.n;j++) printf("%d ",G.edges[i][j]); printf("\n"); } printf("\n");*/ //printf("text\n"); Floyd(G); return 0; }

dp[j][k]= min{ dp[k][k-1]+ dp[k][j][k-1] } 对于这行代码每次验证一个顶点，当验证完第一个顶点完后，接着再验证第二个顶点，第三个顶点直到k=n结束，但我有一个疑惑，当验证第二的的时候这时候，我回过头看了下这里的k（顶点）在被验证时的先后顺序好像并没什么影响，不知道是怎么证明出来的？？？？

#include <iostream> #include <string> #define INFINITY 30000 //定义很大的数 #define MAX_VERTEX_NUM 20//最大的边数 using namespace std; typedef struct{ string vexs[18]; int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵 int vexnum,arcnum;//图的当前定点数和边数 }Graph; void CreateUDN(Graph &G)//创建无向图 { int i,j; G.vexnum = 17; G.arcnum = 21; //初始化各个顶点的信息 G.vexs[1] ="入口"; G.vexs[2] ="人工湖"; G.vexs[3] ="后勤"; G.vexs[4] ="塑胶操场"; G.vexs[5] ="小广场"; G.vexs[6] ="12号楼"; G.vexs[7] ="13号楼"; G.vexs[8] ="学府公寓"; G.vexs[9] ="8号楼"; G.vexs[10] ="三教"; G.vexs[11] ="一教"; G.vexs[12] ="风雨操场"; G.vexs[13] ="第一餐厅"; G.vexs[14] ="排球场"; G.vexs[15] ="图书馆"; G.vexs[16] ="邮局"; G.vexs[17] ="二办"; //初始化存在边的权值 for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) G.arcs[i][j]=INFINITY; G.arcs[0][1]=G.arcs[1][0]=20; G.arcs[0][4]=G.arcs[4][0]=20; G.arcs[1][2]=G.arcs[2][1]=30; G.arcs[2][3]=G.arcs[3][2]=20; G.arcs[2][5]=G.arcs[5][2]=30; G.arcs[4][5]=G.arcs[5][4]=10; G.arcs[5][6]=G.arcs[6][5]=20; G.arcs[5][7]=G.arcs[7][5]=50; G.arcs[6][7]=G.arcs[7][6]=40; G.arcs[6][8]=G.arcs[8][6]=10; G.arcs[7][9]=G.arcs[9][7]=20; G.arcs[7][10]=G.arcs[10][7]=20; G.arcs[8][9]=G.arcs[9][8]=20; G.arcs[8][13]=G.arcs[13][8]=30; G.arcs[9][10]=G.arcs[10][9]=20; G.arcs[10][11]=G.arcs[11][10]=20; G.arcs[11][12]=G.arcs[12][11]=10; G.arcs[12][15]=G.arcs[15][12]=20; G.arcs[13][14]=G.arcs[14][13]=20; G.arcs[14][15]=G.arcs[15][14]=20; G.arcs[15][16]=G.arcs[16][15]=40; } //计算最短路径 void ShortestPath_FLOYD(Graph G,int D[17][17],int P[17][17]) { int u,v,i,j,w; for ( i=0; i<17; ++i) for ( j=0; j<17; ++j) { D[i][j]=G.arcs[i][j];//初始化 P[i][j]= -1;//初始化 } for( u=0; u<17; u++) for (v=0; v<17; v++) for ( w=0; w<17; w++) if (D[v][u]+D[u][w]<D[v][w]) { D[v][w]=D[v][u]+D[u][w]; P[v][w]=u;//u为v到w最短路径上的前驱 } } //输出最短路径上经过的点 void ppath(Graph G,int path[17][17],int i,int j) { int k; k=path[i][j]; if(k==-1) return; ppath(G,path,i,k); cout<<G.vexs[k+1]; cout<<"->"; ppath(G,path,k,j); } int main() { Graph G; CreateUDN(G); while(1) { cout<<"*****欢迎使用校园导航系统*****"<<endl; cout<<"* 1.查看地图 *"<<endl; cout<<"* 2.查询地点信息 *"<<endl; cout<<"* 3.问路系统 *"<<endl; cout<<"* 4.退出系统 *"<<endl; cout<<"******************************"<<endl; int choose; cin>>choose; if(choose == 1) { cout<<"17|"<<endl; cout<<"16|------13"<<endl; cout<<"15| 12|"<<endl; cout<<"14| 11|------8__ |4"<<endl; cout<<" | 10|------| | |" <<endl; cout<<" |______9|______7__|6______|3"<<endl; cout<<" | | "<<endl; cout<<" |5 | "<<endl; cout<<" | __2| "<<endl; cout<<" | _| "<<endl; cout<<" 1_| "<<endl; } if(choose == 2) { int num; cout<<"请输入想要查询地点的编号： "; cin>>num; cout<<G.vexs[num]; cout<<endl; } if(choose == 3) { int v,w; int D[17][17]; int P[17][17]; ShortestPath_FLOYD(G, D, P); cout<<"请输入出发点和目的地的编号："; cin>>v>>w; cout<<"“"; cout<<G.vexs[v]; cout<<"”到“"; cout<<G.vexs[w]; cout<<"”的最短路线长为"<<D[v-1][w-1]<<endl; cout<<"为："; cout<<G.vexs[v]; cout<<"->"; ppath(G,P,v-1,w-1); cout<<G.vexs[w]; cout<<endl; } if(choose == 4) break; } return 0; }

``` #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph; typedef int Patharc[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; /* 构件图 */ void CreateMGraph(MGraph *G) { int i, j; /* printf("请输入边数和顶点数:"); */ G->numEdges=16; G->numVertexes=9; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { G->vexs[i]=i; } for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < G->numVertexes; j++) { if (i==j) G->arc[i][j]=0; else G->arc[i][j] = G->arc[j][i] = INFINITY; } } G->arc[0][1]=1; G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3; G->arc[4][6]=6; G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7; G->arc[7][8]=4; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } /* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */ void ShortestPath_Floyd(MGraph G, Patharc &P, ShortPathTable *D) { int v,w,k; for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */ { for(w=0; w<G.numVertexes; ++w) { (*D)[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */ P[v][w]=w; /* 初始化P */ } } for(k=0; k<G.numVertexes; ++k) { for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { if ((D)[v][w]>(*D)[v][k]+(*D)[k][w]) {/* 如果经过下标为k顶点路径比原两点间路径更短 */ (*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */ p[v][w]=P[v][k];/* 路径设置为经过下标为k的顶点 */ } } } } } int main(void) { int v,w,k; MGraph G; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ CreateMGraph(&G); ShortestPath_Floyd(G,P,&D); printf("各顶点间最短路径如下:\n"); for(v=0; v<G.numVertexes; ++v) { for(w=v+1; w<G.numVertexes; w++) { printf("v%d-v%d weight: %d ",v,w,D[v][w]); k=P[v][w]; /* 获得第一个路径顶点下标 */ printf(" path: %d",v); /* 打印源点 */ while(k!=w) /* 如果路径顶点下标不是终点 */ { printf(" -> %d",k); /* 打印路径顶点 */ k=P[k][w]; /* 获得下一个路径顶点下标 */ } printf(" -> %d\n",w); /* 打印终点 */ } printf("\n"); } printf("最短路径D\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d\t",D[v][w]); } printf("\n"); } printf("最短路径P\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d ",P[v][w]); } printf("\n"); } return 0; } _****_ ```
(*D)[v][w]为何要加上*，不加*程序可以运行但是会出错这是为什么？
![图片说明](https://img-ask.csdn.net/upload/201909/14/1568467927_949056.png) ``` #include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef struct { int vexs[MAXVEX]; int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph; typedef int Patharc[MAXVEX][MAXVEX]; typedef int ShortPathTable[MAXVEX][MAXVEX]; /* 构件图 */ void CreateMGraph(MGraph *G) { int i, j; /* printf("请输入边数和顶点数:"); */ G->numEdges=16; G->numVertexes=9; for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { G->vexs[i]=i; } for (i = 0; i < G->numVertexes; i++)/* 初始化图 */ { for ( j = 0; j < G->numVertexes; j++) { if (i==j) G->arc[i][j]=0; else G->arc[i][j] = G->arc[j][i] = INFINITY; } } G->arc[0][1]=1; G->arc[0][2]=5; G->arc[1][2]=3; G->arc[1][3]=7; G->arc[1][4]=5; G->arc[2][4]=1; G->arc[2][5]=7; G->arc[3][4]=2; G->arc[3][6]=3; G->arc[4][5]=3; G->arc[4][6]=6; G->arc[4][7]=9; G->arc[5][7]=5; G->arc[6][7]=2; G->arc[6][8]=7; G->arc[7][8]=4; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } /* Floyd算法，求网图G中各顶点v到其余顶点w的最短路径P[v][w]及带权长度D[v][w]。 */ void ShortestPath_Floyd(MGraph G, Patharc *P, ShortPathTable *D) { int v,w,k; for(v=0; v<G.numVertexes; ++v) /* 初始化D与P */ { for(w=0; w<G.numVertexes; ++w) { (*D)[v][w]=G.arc[v][w]; /* D[v][w]值即为对应点间的权值 */ (*P)[v][w]=w; /* 初始化P */ } } for(k=0; k<G.numVertexes; ++k) { for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { if ((*D)[v][w]>(*D)[v][k]+(*D)[k][w]) {/* 如果经过下标为k顶点路径比原两点间路径更短 */ (*D)[v][w]=(*D)[v][k]+(*D)[k][w];/* 将当前两点间权值设为更小的一个 */ (*P)[v][w]=(*P)[v][k];/* 路径设置为经过下标为k的顶点 */ } } } } } int main(void) { int v,w,k; MGraph G; Patharc P; ShortPathTable D; /* 求某点到其余各点的最短路径 */ CreateMGraph(&G); ShortestPath_Floyd(G,&P,&D); printf("各顶点间最短路径如下:\n"); for(v=0; v<G.numVertexes; ++v) { for(w=v+1; w<G.numVertexes; w++) { printf("v%d-v%d weight: %d ",v,w,D[v][w]); k=P[v][w]; /* 获得第一个路径顶点下标 */ printf(" path: %d",v); /* 打印源点 */ while(k!=w) /* 如果路径顶点下标不是终点 */ { printf(" -> %d",k); /* 打印路径顶点 */ k=P[k][w]; /* 获得下一个路径顶点下标 */ } printf(" -> %d\n",w); /* 打印终点 */ } printf("\n"); } printf("最短路径D\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d\t",D[v][w]); } printf("\n"); } printf("最短路径P\n"); for(v=0; v<G.numVertexes; ++v) { for(w=0; w<G.numVertexes; ++w) { printf("%d ",P[v][w]); } printf("\n"); } return 0; } ```

Dijkstra Or Floyd Or dfs
Problem Description 在每年的校赛里，所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候，却是非常累的！所以现在他们想要寻找最短的从商店到赛场的路线，你可以帮助他们吗？ Input 输入包括多组数据。每组数据第一行是两个整数N、M（N<=100，M<=10000），N表示成都的大街上有几个路口，标号为1的路口是商店所在地，标号为N的路口是赛场所在地，M则表示在成都有几条路。N=M=0表示输入结束。接下来M行，每行包括3个整数A，B，C（1<=A,B<=N,1<=C<=1000）,表示在路口A与路口B之间有一条路，我们的工作人员需要C分钟的时间走过这条路。 输入保证至少存在1条商店到赛场的路线。 Output 对于每组输入，输出一行，表示工作人员从商店走到赛场的最短时间 Sample Input 2 1 1 2 3 3 3 1 2 5 2 3 5 3 1 2 0 0 Sample Output 3 2

#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> using namespace std; int n = 0; int a[100][100]; int menu() { int m; printf(" 求最小生成树\n"); printf(" ________________________________\n\n"); printf(" 1 输入城市之间的信息\n"); printf(" 2 判断是否能构成一个最小生成树\n"); printf(" 3 查询信息\n"); printf(" 4 退出\n"); printf(" ________________________________\n\n"); printf(" 请输入所选功能1--4\n"); scanf("%d",&m); return m; } void xin_input() { printf("1 遍历所有城市的最小生成树\n"); printf("2 查询两个城市之间的距离\n"); printf("3 退出\n"); //printf("________________________________\n\n"); } //以下为克鲁斯卡尔算法 typedef struct node //构造一个结构体，两个城市可以看成起点和终点，之间的路道可以看成一个边 { int st; //起点 int ed; //终点 int dis;//距离 }node; node p[1000]; int pre[1000],rank[1000]; bool cmp(node p1,node p2) { return p1.dis < p2.dis; } //下面三个函数是并查集，其作用是检验当一条边添加进去，是否会产生回路 void set(int x) { pre[x] = x;//初始化 rank[x] = 0; } int find(int x)//找到这个点的祖先 { if(x != pre[x]) pre[x] = find(pre[x]); return pre[x]; } void Union(int x,int y)//将这两个添加到一个集合里去 { x = find(x); y = find(y); if(rank[x] >= rank[y]) { pre[y] = x; rank[x] ++; } else pre[y] = x; } void Kruskal() // { int ans = 0,i,j,k = 0; for(i = 1;i <= n;i ++) set(i); for(i = 1;i <= n;i ++) for(j = i + 1;j <= n;j ++) { p[++k].st = i; p[k].ed = j; p[k].dis = a[i][j]; //先把所有城市之间的路段看成一个边 } sort(p + 1,p + k + 1,cmp);//把所有的边按从小到大进行排序 int count = 0; for(i = 1;i <= k;i ++) { if(find(p[i].st) != find(p[i].ed))//如果这两点连接在一起不构成一个回路，则执行下面操作 { printf("第%d条路段为：%d--%d,权值为%d\n",++ count,p[i].st,p[i].ed,p[i].dis);//将这条边的起点、终点打印出来 ans += p[i].dis; //说明这条路段要用 Union(p[i].st,p[i].ed); } } printf("遍历所有城市的最短路程为: %d\n",ans);//最短遍历的路程 //printf("________________________________\n"); } //普里姆算法 int prim() { int close[100],low[100],i,j,ans = 0;//close[j]表示离j最近的顶点，low[j]表示离j最短的距离 bool use[100]; use[1] = 1; for(i = 2;i <= n;i ++) { low[i] = a[1][i]; //初始化 close[i] = 1; use[i] = 0; } for(i = 1;i < n;i ++) { int min = 100000000,k = 0; for(j = 2;j <= n;j ++) { if(use[j] == 0 && min > low[j])//找到最小的low[]值，并记录 { min = low[j]; k = j; } } //printf("%d %d\n",close[k],k); for(j = 2;j <= n;j ++) { if(use[j] == 0 && low[j] > a[k][j]) { low[j] = a[k][j]; //修改low[]值和close[]值 close[j] = k; } } ans += a[close[k]][k]; } return ans; } //求最短路径-单源点到其余点的最短路径(Dijkstra算法) void ShortestPath_DIJ(int x,int y) //X指单源点，y指目标点 { int i,d[100],j; bool use[100]; for(i = 1;i <= n;i ++) { use[i] = 0; //初始化 d[i] = a[x][i]; } use[x] = 1;//这个点肯定用过 d[x] = 0; for(i = 1;i < n;i ++)//执行n-1次操作 { int min = 100000000,v; for(j = 1;j <= n;j ++) { if(use[j] == 0 && min > d[j])//找出最短距离的 { min = d[j]; v = j; } } use[v] = 1; for(j = 1;j <= n;j ++) { if(use[j] == 0 && d[j] > min + a[v][j])//修改d[]的值 { d[j] = min + a[v][j]; } } } printf("%d城市到城市%d的最短距离为: %d\n",x,y,d[y]); } //求每一对顶点之间的最短路径(Floyd算法) int b[100][100]; void ShortestPath_FLOYD() //这个算法耗时多(n^3),不过容易理解 { int i,j,k; for(i = 1;i <= n;i ++) for(j = 1;j <= n;j ++) b[i][j] = a[i][j]; //先b[][]进行保存，避免a[][]的值发生变化 for(k = 1;k <= n;k ++) for(i = 1;i <= n;i ++) for(j = 1;j <= n;j ++) if(b[i][j] > b[i][k] + b[k][j]) b[i][j] = b[i][k] + b[k][j]; while(1) { int st,ed; printf("请输入两个城市的编号:\n");//对此进行多次操作 scanf("%d%d",&st,&ed); printf("%d 城市到 %d 城市的最短距离为: %d\n",st,ed,b[st][ed]); //printf("________________________________\n"); char str[100]; printf("是否要继续? yes or no\n"); scanf("%s",str); if(strcmp(str,"no") == 0) { //printf("________________________________\n"); break; } } } void shuru()//输入城市信息 { int i,j; if(n != 0) { char str[100]; printf("是否要确定输入新的城市之间的信息? yes or no ?\n"); scanf("%s",str); if(strcmp(str,"no") == 0) { return ; } } printf("请输入城市的个数:\n"); scanf("%d",&n); printf("输入%d个城市的邻接矩阵:\n",n); for(i = 1;i <= n;i ++) { for(j = 1;j <= n;j ++) scanf("%d",&a[i][j]); } //printf("________________________________\n"); } void chaxun() //一个查徇两个城市最短径的操作 { while(1) { int t1,t2; printf("输入第一个城市的编号:\n"); scanf("%d",&t1); printf("输入第二个城市的编号:\n"); scanf("%d",&t2); ShortestPath_DIJ(t1,t2);//调用 char str[100]; printf("是否要继续? yes or no\n"); scanf("%s",str); if(strcmp(str,"no") == 0) { //printf("________________________________\n"); break; } } } void chaxun_func() { if(n == 0) { printf("这里没有城市之间的信息\n"); return; } xin_input(); printf("请选择以上功能:1-3\n"); int m1; scanf("%d",&m1); printf("\n"); if(m1 == 1) Kruskal(); else if(m1 == 2) { chaxun(); } //else // break; } void judge() { int ans; ans = prim(); if(ans >= 100000000) printf("不能构成最小生成树\n"); else printf("能构成最小生成树\n"); } int main() { while(1) { switch(menu()) { case 1:shuru();break; case 2:judge();break; case 3: chaxun_func();break; case 4:goto loop; } } loop:; return 0; }
c语言实现的套汇问题 钱的种类多了就就不行了

# 可从后往前看，来自学生党的求助，缺的都是iostream ## #include "pch.h"， ## #include "Graph.h" Edge::Edge() { from = -1; to = -1; weight = 0; } Edge::Edge(int f, int t, int w) { from = f; to = t; weight = w; } Graph::Graph() { } Graph::Graph(int numVert) { numVertex = numVert; numEdge = 0; Indegree = new int[numVertex]; Mark = new int[numVertex]; for (int i = 0; i < numVertex; i++) { Mark[i] = UNVISITED; Indegree[i] = 0; } } Graph::~Graph() { delete[] Mark; delete[] Indegree; } bool Graph::IsEdge(Edge oneEdge) { if (oneEdge.weight > 0 && oneEdge.weight < INFINITYS && oneEdge.to >= 0) return true; else return false; } void Graph::clearVisitedMark() { for (int i = 0; i < numVertex; i++) Mark[i] = UNVISITED; } #pragma once #include <iostream> using namespace std; #define MAX 102 #define INFINITYS 65536 #define UNVISITED 0 #define VISITED 1 #ifndef GRAPH_H #define GRAPH_H class Edge { public: Edge(); Edge(int f, int t, int w); ~Edge() {} bool operator < (const Edge &arg) { return (this->weight < arg.weight); } bool operator == (const Edge &arg) { return (this->weight == arg.weight); } bool operator > (const Edge &arg) { return (this->weight > arg.weight); } bool operator <= (const Edge &arg) { return (this->weight <= arg.weight); } bool operator >= (const Edge &arg) { return (this->weight >= arg.weight); } int from; int to; int weight; }; class Graph { public: Graph(); Graph(int numVert); virtual ~Graph(); int VerticesNum() { return numVertex; } int EdgesNum() { return numEdge; } bool IsEdge(Edge oneEdge); int FromVertex(Edge oneEdge) { return oneEdge.from; } int ToVertex(Edge oneEdge) { return oneEdge.to; } int Weight(Edge oneEdge) { return oneEdge.weight; } void clearVisitedMark(); /*virtual Edge FirstEdge(int oneVertex) = 0; virtual Edge NextEdge(Edge preEdge) = 0; virtual void setEdge(int from, int to, int weight) = 0; virtual void delEdge(int from, int to) = 0;*/ protected: int numVertex; int numEdge; int * Mark; int * Indegree; }; #endif // !GRAPH_H #include "pch.h" #include "Graphm.h" Graphm::Graphm() { } Graphm::~Graphm() { for (int i = 0; i < numVertex; i++) delete[] matrix[i]; delete[] matrix; } Edge Graphm::FristEdge(int oneVertex) { Edge myEdge; myEdge.from = oneVertex; for (int i = 0; i < numVertex; i++) if (matrix[oneVertex][i] != 0 && matrix[oneVertex][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[oneVertex][i]; break; } return myEdge; } Edge Graphm::NextEdge(Edge preEdge) { Edge myEdge; myEdge.from = preEdge.from; if (preEdge.to < numVertex) for (int i = preEdge.to + 1; i < numVertex; i++) if (matrix[preEdge.from][i] != 0 && matrix[preEdge.from][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[preEdge.from][i]; break; } return myEdge; } void Graphm::setEdge(int from, int to, int weight) { if (matrix[from][to] <= 0) { numEdge++; Indegree[to]++; } matrix[from][to] = weight; } void Graphm::delEdge(int from, int to) { if (matrix[from][to] > 0) { numEdge--; Indegree[to]--; } matrix[from][to] = 0; } void Graphm::InitWith2DimArray(int * mat, int row_col) { for (int i = 0; i < row_col; i++) for (int j = 0; j < row_col; j++) { cout << *(mat + i * row_col + j) << ", \n"; this->setEdge(i, j, *(mat + i * row_col + j)); } cout << endl; } void Graphm::DFS_ConnectedSubGraph(int n) { this->Mark[n] = VISITED; Visit(n); for (Edge e = this->FristEdge(n); this->IsEdge(e); e = this->NextEdge(e)) if (this->Mark[this->ToVertex(e)] == UNVISITED) DFS_ConnectedSubGraph(this->ToVertex(e)); } void Graphm::BFS_ConnectedSubGraph(int n) { queue<int> Q; Visit(n); Mark[n] = VISITED; Q.push(n); while (! Q.empty()) { int u = Q.front(); Q.pop(); for(Edge e = FristEdge(u); IsEdge(e); e = NextEdge(e)) if (Mark[ToVertex(e)] == UNVISITED) { Visit(ToVertex(e)); Mark[ToVertex(e)] = VISITED; Q.push(ToVertex(e)); } } } #pragma once #include "Graph.h" #include <queue> #ifndef GRAGHM_H #define GRAGHM_H class Graphm : public Graph { public: Graphm(); Graphm(int n) : Graph(n) { int i; matrix = (int **) new int *[numVertex]; for (i = 0; i < numVertex; i++) matrix[i] = new int[numVertex]; for (i = 0; i < numVertex; i++) for (int j = 0; j < numVertex; j++) matrix[i][j] = 0; } ~Graphm(); Edge FristEdge(int oneVertex); Edge NextEdge(Edge preEdge); void setEdge(int from, int to, int weight); void delEdge(int from, int to); void InitWith2DimArray(int * mat, int row_col); void DFS_ConnectedSubGraph(int n); void BFS_ConnectedSubGraph(int n); void Visit(int n) { cout << 'n' << n << " \n"; } //private: int ** matrix; }; #endif // !GRAGHM_H // main.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include "pch.h" #include <iostream> #include "Floyd.h" const int const vertexesNum = 5; int matrix1[vertexesNum][vertexesNum] = { 0 , 8 , INFINITYS, 4 , 3 , INFINITYS, 0 , INFINITYS, INFINITYS, 8 , 6 , 7 , 0 , 10 , 2 , INFINITYS, INFINITYS, INFINITYS, 0 , INFINITYS, 5 , 5 , INFINITYS, INFINITYS, 0 }; int BrokerToPassRomour(Graphm & G, Dist ** D); int main() { std::cout << "Hello World!\n"; Graphm mat[vertexesNum]; mat->InitWith2DimArray((int *)matrix1, vertexesNum); cout << endl; cout << "深度优先周游：\n" << endl; int i; for (i = 0; i < vertexesNum; i++) { mat->clearVisitedMark(); mat->DFS_ConnectedSubGraph(i); cout << endl; } cout << endl; cout << "广度优先周游：\n" << endl; for (i = 0; i < vertexesNum; i++) { mat->clearVisitedMark(); mat->BFS_ConnectedSubGraph(i); cout << endl; } cout << endl; Dist ** floydResult; createFloydResult(floydResult, vertexesNum); int startVertex = BrokerToPassRomour(mat[0], floydResult); cout << "所有顶点间的最短路径：\n" << endl; printAllDistances(floydResult, vertexesNum); cout << endl; for (i = 0; i < vertexesNum; i++) for (int j = 0; j < vertexesNum; j++) if (i != j) printOnePath(floydResult, vertexesNum, i, j); cout << endl; deleteFloydResult(floydResult, vertexesNum); if (startVertex >= 0) cout << "谣言应从 n \n" << startVertex << " 点开始传播！\n" << endl; else cout << "图不连通，问题无解 \n" << endl; return 0; } // 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单 // 调试程序: F5 或调试 >“开始调试”菜单 // 入门提示: // 1. 使用解决方案资源管理器窗口添加/管理文件 // 2. 使用团队资源管理器窗口连接到源代码管理 // 3. 使用输出窗口查看生成输出和其他消息 // 4. 使用错误列表窗口查看错误 // 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目 // 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件 int BrokerToPassRomour(Graphm & G, Dist ** D) { int * max; max = new int[G.VerticesNum()]; int min = 0; int pos = 0; int i = 0; for (i = 0; i < G.VerticesNum(); i++) max[i] = -1; Floyd(G, D); for (i = 0; i < G.VerticesNum(); i++) for (int j = 0; j < G.VerticesNum(); j++) if (D[i][j].length > max[i]) max[i] = D[i][j].length; min = max[0]; for (i = 1; i < G.VerticesNum(); i++) if (max[i] < min) { min = max[i]; pos = i; } if (min == INFINITYS) { cout << "此图不连通 \n" << endl; return -1; } return pos; } // pch.cpp: 与预编译标头对应的源文件；编译成功所必需的 #include "pch.h" // 一般情况下，忽略此文件，但如果你使用的是预编译标头，请保留它。 // 入门提示: // 1. 使用解决方案资源管理器窗口添加/管理文件 // 2. 使用团队资源管理器窗口连接到源代码管理 // 3. 使用输出窗口查看生成输出和其他消息 // 4. 使用错误列表窗口查看错误 // 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目 // 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件 #ifndef PCH_H #define PCH_H // TODO: 添加要在此处预编译的标头 #endif //PCH_H #include "pch.h" #include "Floyd.h" void createFloydResult(Dist **& D, int vertexesNum) { D = new Dist *[vertexesNum]; for (int i = 0; i < vertexesNum; i++) D[i] = new Dist[vertexesNum]; } void deleteFloydResult(Dist **& D, int vertexesNum) { for (int i = 0; i < vertexesNum; i++) delete[] D[i]; delete[] D; D = NULL; } void printAllDistances(Dist ** D, int vertexesNum) { for (int i = 0; i < vertexesNum; i++) { for (int j = 0; j < vertexesNum; j++) cout << D[i][j].length << " , \n"; cout << endl; } } void printOnePath(Dist ** D, int vertexesNum, int start, int end) { if (D[start][end].length == INFINITYS) return; int * path = new int[vertexesNum]; int vertexCount = 0; int tail = end; while (tail != start) { path[vertexCount++] = D[start][tail].pre; tail = D[start][tail].pre; } cout << "n" << start << "->n" << end << " : "; for (int i = vertexCount - 1; i >= 0; i--) cout << "n" << path[i] << "->"; cout << "n" << end << endl; delete[] path; } void Floyd(Graphm & G, Dist ** D) { int i, j, v; D = new Dist *[G.VerticesNum()]; for (i = 0; i < G.VerticesNum(); i++) D[i] = new Dist[G.VerticesNum()]; for (i = 0; i < G.VerticesNum(); i++) for (j = 0; j < G.VerticesNum(); j++) { if (i == j) { D[i][j].length = 0; D[i][j].pre = i; } else { D[i][j].length = INFINITYS; D[i][j].pre = -1; } } for (i = 0; i < G.VerticesNum(); i++) for (Edge e = G.FristEdge(i); G.IsEdge(e); e = G.NextEdge(e)) { D[i][G.ToVertex(e)].length = G.Weight(e); D[i][G.ToVertex(e)].pre = i; } for (v = 0; v < G.VerticesNum(); v++) for (i = 0; i < G.VerticesNum(); i++) for (j = 0; j < G.VerticesNum(); j++) if (D[i][j].length > (D[i][v].length + D[v][j].length)) { D[i][j].length = D[i][v].length + D[v][j].length; D[i][j].pre = D[v][j].pre; } } #pragma once #include "Graphm.h" #ifndef FLOYD_H #define FLOYD_H class Dist { public: Dist() {} ~Dist() {} int index; int length; int pre; bool operator < (const Dist &arg) { return (length < arg.length); } bool operator == (const Dist &arg) { return (length == arg.length); } bool operator > (const Dist &arg) { return (length > arg.length); } bool operator <= (const Dist &arg) { return (length <= arg.length); } bool operator >= (const Dist &arg) { return (length >= arg.length); } }; void createFloydResult(Dist ** &D, int vertexesNum); void deleteFloydResult(Dist ** &D, int vertexesNum); void printAllDistances(Dist ** D, int vertexesNum); void printOnePath(Dist ** D, int vertexesNum, int start, int end); void Floyd(Graphm &G, Dist ** D); #endif // !FLOYD_H ********************************************************************* "Graphm.cpp": #include "pch.h" #include "Graphm.h" Graphm::Graphm() { } Graphm::~Graphm() { for (int i = 0; i < numVertex; i++) delete[] matrix[i]; delete[] matrix; } Edge Graphm::FristEdge(int oneVertex) { Edge myEdge; myEdge.from = oneVertex; for (int i = 0; i < numVertex; i++) if (matrix[oneVertex][i] != 0 && matrix[oneVertex][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[oneVertex][i]; break; } return myEdge; } Edge Graphm::NextEdge(Edge preEdge) { Edge myEdge; myEdge.from = preEdge.from; if (preEdge.to < numVertex) for (int i = preEdge.to + 1; i < numVertex; i++) if (matrix[preEdge.from][i] != 0 && matrix[preEdge.from][i] < INFINITYS) { myEdge.to = i; myEdge.weight = matrix[preEdge.from][i]; break; } return myEdge; } void Graphm::setEdge(int from, int to, int weight) { if (matrix[from][to] <= 0) { numEdge++; Indegree[to]++; } matrix[from][to] = weight; } void Graphm::delEdge(int from, int to) { if (matrix[from][to] > 0) { numEdge--; Indegree[to]--; } matrix[from][to] = 0; } void Graphm::InitWith2DimArray(int * mat, int row_col) { for (int i = 0; i < row_col; i++) for (int j = 0; j < row_col; j++) { cout << *(mat + i * row_col + j) << ", \n"; this->setEdge(i, j, *(mat + i * row_col + j)); } cout << endl; } void Graphm::DFS_ConnectedSubGraph(int n) { this->Mark[n] = VISITED; Visit(n); for (Edge e = this->FristEdge(n); this->IsEdge(e); e = this->NextEdge(e)) if (this->Mark[this->ToVertex(e)] == UNVISITED) DFS_ConnectedSubGraph(this->ToVertex(e)); } void Graphm::BFS_ConnectedSubGraph(int n) { queue<int> Q; Visit(n); Mark[n] = VISITED; Q.push(n); while (! Q.empty()) { int u = Q.front(); Q.pop(); for(Edge e = FristEdge(u); IsEdge(e); e = NextEdge(e)) if (Mark[ToVertex(e)] == UNVISITED) { Visit(ToVertex(e)); Mark[ToVertex(e)] = VISITED; Q.push(ToVertex(e)); } } } ************************************************************** 第51行 if (matrix[from][to] <= 0) //void Graphm::setEdge(int from, int to, int weight) 引发了未经处理的异常:读取访问权限冲突。 this->matrix 是 0xCDDDCDDE
Risk(Floyd)
Risk is a board game in which several opposing players attempt to conquer the world. The gameboard consists of a world map broken up into hypothetical countries. During a player's turn, armies stationed in one country are only allowed to attack only countries with which they share a common border. Upon conquest of that country, the armies may move into the newly conquered country. During the course of play, a player often engages in a sequence of conquests with the goal of transferring a large mass of armies from some starting country to a destination country. Typically, one chooses the intervening countries so as to minimize the total number of countries that need to be conquered. Given a description of the gameboard with 20 countries each with between 1 and 19 connections to other countries, your task is to write a function that takes a starting country and a destination country and computes the minimum number of countries that must be conquered to reach the destination. You do not need to output the sequence of countries, just the number of countries to be conquered including the destination. For example, if starting and destination countries are neighbors, then your program should return one. The following connection diagram illustrates the sample input. Input Input to your program will consist of a series of country configuration test sets. Each test set will consist of a board description on lines 1 through 19. The representation avoids listing every national boundary twice by only listing the fact that country I borders country J when I < J. Thus, the Ith line, where I is less than 20, contains an integer X indicating how many "higher-numbered" countries share borders with country I, then X distinct integers J greater than I and not exceeding 20, each describing a boundary between countries I and J. Line 20 of the test set contains a single integer (1 <= N <= 100) indicating the number of country pairs that follow. The next N lines each contain exactly two integers (1 <= A,B <= 20; A!=B) indicating the starting and ending countries for a possible conquest. There can be multiple test sets in the input; your program should continue reading and processing until reaching the end of file. There will be at least one path between any two given countries in every country configuration. Output For each input set, your program should print the following message "Test Set #T" where T is the number of the test set starting with 1. The next NT lines each will contain the result for the corresponding test in the test set - that is, the minimum number of countries to conquer. The test result line should contain the start country code A the string " to " the destination country code B ; the string ": " and a single integer indicating the minimum number of moves required to traverse from country A to country B in the test set. Following all result lines of each input set, your program should print a single blank line. Sample Input 1 3 2 3 4 3 4 5 6 1 6 1 7 2 12 13 1 8 2 9 10 1 11 1 11 2 12 17 1 14 2 14 15 2 15 16 1 16 1 19 2 18 19 1 20 1 20 5 1 20 2 9 19 5 18 19 16 20 Sample Output Test Set #1 1 to 20: 7 2 to 9: 5 19 to 5: 6 18 to 19: 2 16 to 20: 2
e-Market 的计算的问题

![图片说明](https://img-ask.csdn.net/upload/201512/14/1450105965_975066.png) #include<stdio.h> #include<string.h> #include<malloc.h> #include<stdlib.h> typedef char InfoPtr; typedef char VertexType[4]; typedef int VRType; #define INFINITY 100000 #define MAXSIZE 100 typedef int PathMatrix[MAXSIZE][MAXSIZE][MAXSIZE]; typedef int ShortPathLength[MAXSIZE][MAXSIZE]; typedef enum{DG, DN, UG, UN }GraphKind; typedef struct { VRType adj; InfoPtr *info; }ArcNode, AdjMatrix[MAXSIZE][MAXSIZE]; typedef struct { VertexType vex[MAXSIZE]; AdjMatrix arc; int vexnum, arcnum; GraphKind kind; }MGraph; typedef struct { int row; int col; int weight; } GNode; void CreateGraph(MGraph *N, GNode *value, int vnum, int arcnum, VertexType *ch); void DisplayGraph(MGraph N); void Floyd(MGraph N, PathMatrix path, ShortPathLength dist); void main() { int w, u, v, vnum = 3, arcnum = 4; MGraph N; GNode value[] = {{0,1,5}, {1,0,10}, {1,2,6}, {2,0,9}}; VertexType ch[] = {"v0", "v1", "v2"}; PathMatrix path; ShortPathLength dist; CreateGraph(&N, value, vnum, arcnum, ch); for(v = 0; v < N.vexnum; v++) N.arc[v][v].adj = 0; DisplayGraph(N); Floyd(N, path, dist); printf("顶点之间的最短路径长度矩阵dist:\n"); for(u = 0; u < N.vexnum; u++) { for(v = 0; v < N.vexnum; v++) printf("%6d", dist[u][v]); printf("\n"); } for(u = 0; u < N.vexnum; u++) for(v = 0; v < N.vexnum; v++) if(u != v) printf("%s到%s的最短路径为%d\n", N.vex[u], N.vex[v], dist[u][v]); printf("各顶点之间的最短路径所经过的顶点:\n"); for(u = 0; u < N.vexnum; u++) for(v = 0; v < N.vexnum; v++) if(u != v) { printf("由%s到%s经过: ", N.vex[u], N.vex[v]); for(w = 0; w < N.vexnum; w++) if(path[u][v][w] == 1) printf("%s ", N.vex[w]); printf("\n"); } } void CreateGraph(MGraph *N, GNode *value, int vnum, int arcnum, VertexType *ch) { int i, j, k, w, InfoFlag, len; char s[MAXSIZE]; VertexType v1, v2; N->vexnum = vnum; N->arcnum = arcnum; for(i = 0; i < vnum; i++) strcpy(N->vex[i], ch[i]); for(i = 0; i < N->vexnum; i++) for(j = 0; j < N->vexnum; j++) { N->arc[i][j].adj = INFINITY; N->arc[i][j].info = NULL; } for(k = 0; k < arcnum; k++) { i = value[k].row; j = value[k].col; N->arc[i][j].adj = value[k].weight; } N->kind = DN; } void DisplayGraph(MGraph N) { int i, j; printf("有向网具有%d个顶点%d条弧，顶点依次是：", N.vexnum, N.arcnum); for(i = 0; i < N.vexnum; ++i) { printf("%s ", N.vex[i]); } printf("\n有向网N的：\n"); printf("序号i="); for(i = 0; i < N.vexnum; i++) { printf("%11d", i); } printf("\n"); for(i = 0; i < N.vexnum; i++) { printf(" %6-d ", i); for(j = 0; j < N.vexnum; j++) printf("%-11d", N.arc[i][j].adj); printf("\n"); } } void Floyd(MGraph N, PathMatrix path, ShortPathLength dist) { int u, v, w, i; for(v = 0; v < N.vexnum; v++) for(w = 0; w < N.vexnum; w++) { dist[v][w] = N.arc[v][w].adj; for(u = 0; u < N.vexnum; u++) path[v][w][u] = 0; if(dist[v][w] < INFINITY) { path[v][w][v] = 1; path[v][w][w] = 1; } } for(u = 0; u < N.vexnum; u++) for(v = 0; v < N.vexnum; v++) for(w = 0; w < N.vexnum; w++) if(dist[v][u] < INFINITY && dist[u][w] < INFINITY && dist[v][u] + dist[u][w] < dist[v][w]) { dist[v][w] = dist[v][u] + dist[u][w]; for(i = 0; i < N.vexnum; i++) path[v][w][i] = path[v][u][i] || path[u][w][i]; } }
130 个相见恨晚的超实用网站，一次性分享出来

win10系统安装教程（U盘PE+UEFI安装）

Python——画一棵漂亮的樱花树（不同种樱花+玫瑰+圣诞树喔）

《奇巧淫技》系列-python！！每天早上八点自动发送天气预报邮件到QQ邮箱

Java描述设计模式(19)：模板方法模式

11月8日，由中国信息通信研究院、中国通信标准化协会、中国互联网协会、可信区块链推进计划联合主办，科技行者协办的2019可信区块链峰会将在北京悠唐皇冠假日酒店开幕。 　　区块链技术被认为是继蒸汽机、电力、互联网之后，下一代颠覆性的核心技术。如果说蒸汽机释放了人类的生产力，电力解决了人类基本的生活需求，互联网彻底改变了信息传递的方式，区块链作为构造信任的技术有重要的价值。 　　1...
C语言魔塔游戏

8年经验面试官详解 Java 面试秘诀

Linux网络服务-----实验---PXE和Kickstart的无人值守装机

A*搜索算法概述

Java工作4年来应聘要16K最后没要,细节如下。。。

2020年，冯唐49岁：我给20、30岁IT职场年轻人的建议

CPU对每个程序员来说，是个既熟悉又陌生的东西？ 如果你只知道CPU是中央处理器的话，那可能对你并没有什么用，那么作为程序员的我们，必须要搞懂的就是CPU这家伙是如何运行的，尤其要搞懂它里面的寄存器是怎么一回事，因为这将让你从底层明白程序的运行机制。 随我一起，来好好认识下CPU这货吧 把CPU掰开来看 对于CPU来说，我们首先就要搞明白它是怎么回事，也就是它的内部构造，当然，CPU那么牛的一个东...

Linux自学篇——linux命令英文全称及解释
man: Manual 意思是手册，可以用这个命令查询其他命令的用法。 pwd：Print working directory 意思是密码。 su：Swith user 切换用户，切换到root用户 cd：Change directory 切换目录 ls：List files 列出目录下的文件 ps：Process Status 进程状态 mkdir：Make directory ...
Python实战：抓肺炎疫情实时数据，画2019-nCoV疫情地图

NO.1 　有20瓶药丸，其中19瓶装有1克/粒的药丸，余下一瓶装有1.1克/粒的药丸。给你一台称重精准的天平，怎么找出比较重的那瓶药丸？天平只能用一次。 解法 有时候，严格的限制条件有可能反倒是解题的线索。在这个问题中，限制条件是天平只能用一次。 因为天平只能用一次，我们也得以知道一个有趣的事实：一次必须同时称很多药丸，其实更准确地说，是必须从19瓶拿出药丸进行称重。否则，如果跳过两瓶或更多瓶药...