目录

一、迪杰斯特拉算法

1、算法描述

2、C语言代码

二、弗洛伊德算法

1、算法描述

2、C语言代码

一、迪杰斯特拉算法

1、算法描述

迪杰斯特拉算法计算的是网中的一个顶点到其它顶点的最短路径问题。

2、C语言代码

#include <stdio.h>#define MAX_VERtEX_NUM 20 //顶点的最大个数#define VRType int//表示弧的权值的类型#define VertexType int //图中顶点的数据类型#define INFINITY 65535typedef struct {VertexType vexs[MAX_VERtEX_NUM]; //存储图中顶点数据VRType arcs[MAX_VERtEX_NUM][MAX_VERtEX_NUM];//二维数组，记录顶点之间的关系int vexnum,arcnum; //记录图的顶点数和弧（边）数}MGraph;typedef int PathMatrix[MAX_VERtEX_NUM];//用于存储最短路径中经过的顶点的下标typedef int ShortPathTable[MAX_VERtEX_NUM]; //用于存储各个最短路径的权值和//根据顶点本身数据，判断出顶点在二维数组中的位置int LocateVex(MGraph * G,VertexType v){int i=0;//遍历一维数组，找到变量vfor (; i<G->vexnum; i++) {if (G->vexs[i]==v) {break;}}//如果找不到，输出提示语句，返回-1if (i>G->vexnum) {printf("no such vertex.\n");return -1;}return i;}//构造有向网void CreateUDG(MGraph *G){printf("请输入无向网的顶点数和边数：\n");scanf("%d %d",&(G->vexnum),&(G->arcnum));printf("请输入无向网的顶点：\n");for (int i=0; i<G->vexnum; i++) {scanf("%d",&(G->vexs[i]));}for (int i=0; i<G->vexnum; i++) {for (int j=0; j<G->vexnum; j++) {G->arcs[i][j]=INFINITY;}}printf("请输入无向网弧的两个顶点和权值：\n");for (int i=0; i<G->arcnum; i++) {int v1,v2,w;scanf("%d %d %d",&v1,&v2,&w);int n=LocateVex(G, v1);int m=LocateVex(G, v2);if (m==-1 ||n==-1) {printf("no this vertex\n");return;}G->arcs[n][m]=w;}}//迪杰斯特拉算法，v0表示有向网中起始点所在数组中的下标void ShortestPath_Dijkstra(MGraph G,int v0,PathMatrix *p,ShortPathTable *D){int final[MAX_VERtEX_NUM];//用于存储各顶点是否已经确定最短路径的数组//对各数组进行初始化for (int v=0; v<G.vexnum; v++) {final[v]=0;(*D)[v]=G.arcs[v0][v];(*p)[v]=0;}//由于以v0位下标的顶点为起始点，所以不用再判断(*D)[v0]=0;final[v0]=1;int k = 0;for (int i=0; i<G.vexnum; i++) {int min=INFINITY;//选择到各顶点权值最小的顶点，即为本次能确定最短路径的顶点for (int w=0; w<G.vexnum; w++) {if (!final[w]) {if ((*D)[w]<min) {k=w;min=(*D)[w];}}}//设置该顶点的标志位为1，避免下次重复判断final[k]=1;//对v0到各顶点的权值进行更新for (int w=0; w<G.vexnum; w++) {if (!final[w]&&(min+G.arcs[k][w]<(*D)[w])) {(*D)[w]=min+G.arcs[k][w];(*p)[w]=k;//记录各个最短路径上存在的顶点}}}}int main(){MGraph G;CreateUDG(&G);PathMatrix P;ShortPathTable D;ShortestPath_Dijkstra(G, 0, &P, &D);for (int i=1; i<G.vexnum; i++) {printf("V%d - V%d的最短路径中的顶点有(逆序)：",0,i);printf(" V%d",i);int j=i;//由于每一段最短路径上都记录着经过的顶点，所以采用嵌套的方式输出即可得到各个最短路径上的所有顶点while (P[j]!=0) {printf(" V%d",P[j]);j=P[j];}printf(" V0\n");}printf("源点到各顶点的最短路径长度为:\n");for (int i=1; i<G.vexnum; i++) {printf("V%d - V%d : %d \n",G.vexs[0],G.vexs[i],D[i]);}return 0;}

二、弗洛伊德算法

1、算法描述

弗洛伊德算法计算的是网中的一个顶点到其它顶点的最短路径问题。

对于网中的任意两个顶点来说，之间的最短路径有两种情况：

直接从顶点A到顶点B的弧的权值为顶点A到顶点B的最短路径从顶点A开始，经过若干个顶点，最终到达顶点B，期间经过的弧的权值和为从顶点A到顶点B的最短路径

判断存在一条权值更小的路径：

Dis(A,K) + Dis(K,B) <= Dis(A,B)

其中，K表示网中的所有顶点，Dis(A,B)表示顶点A到顶点B的距离。

2、C语言代码

#include <stdio.h>#define MAX_VERtEX_NUM 20 //顶点的最大个数#define VRType int//表示弧的权值的类型#define VertexType int //图中顶点的数据类型#define INFINITY 65535typedef struct {VertexType vexs[MAX_VERtEX_NUM]; //存储图中顶点数据VRType arcs[MAX_VERtEX_NUM][MAX_VERtEX_NUM];//二维数组，记录顶点之间的关系int vexnum,arcnum; //记录图的顶点数和弧（边）数}MGraph;typedef int PathMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];//用于存储最短路径中经过的顶点的下标typedef int ShortPathTable[MAX_VERtEX_NUM][MAX_VERtEX_NUM]; //用于存储各个最短路径的权值和//根据顶点本身数据，判断出顶点在二维数组中的位置int LocateVex(MGraph * G,VertexType v){int i=0;//遍历一维数组，找到变量vfor (; i<G->vexnum; i++) {if (G->vexs[i]==v) {break;}}//如果找不到，输出提示语句，返回-1if (i>G->vexnum) {printf("no such vertex.\n");return -1;}return i;}//构造有向网void CreateUDG(MGraph *G){printf("请输入无向网的顶点数和边数：\n");scanf("%d %d",&(G->vexnum),&(G->arcnum));printf("请输入无向网的顶点：\n");for (int i=0; i<G->vexnum; i++) {scanf("%d",&(G->vexs[i]));}for (int i=0; i<G->vexnum; i++) {for (int j=0; j<G->vexnum; j++) {G->arcs[i][j]=INFINITY;}}printf("请输入无向网弧的两个顶点和权值：\n");for (int i=0; i<G->arcnum; i++) {int v1,v2,w;scanf("%d %d %d",&v1,&v2,&w);int n=LocateVex(G, v1);int m=LocateVex(G, v2);if (m==-1 ||n==-1) {printf("no this vertex\n");return;}G->arcs[n][m]=w;}}//弗洛伊德算法，其中P二维数组存放各对顶点的最短路径经过的顶点，D二维数组存储各个顶点之间的权值void ShortestPath_Floyed(MGraph G,PathMatrix *P,ShortPathTable *D){//对P数组和D数组进行初始化for (int v=0; v<G.vexnum; v++) {for (int w=0; w<G.vexnum; w++) {(*D)[v][w]=G.arcs[v][w];(*P)[v][w]=-1;}}//拿出每个顶点作为遍历条件for (int k=0; k<G.vexnum; k++) {//对于第k个顶点来说，遍历网中任意两个顶点，判断间接的距离是否更短for (int v=0; v<G.vexnum; v++) {for (int w=0; w<G.vexnum; w++) {//判断经过顶点k的距离是否更短，如果判断成立，则存储距离更短的路径if ((*D)[v][w] > (*D)[v][k] + (*D)[k][w]) {(*D)[v][w]=(*D)[v][k] + (*D)[k][w];(*P)[v][w]=k;}}}}}int main(){MGraph G;CreateUDG(&G);PathMatrix P;ShortPathTable D;ShortestPath_Floyed(G, &P, &D);printf("--------------------\n");for (int i=0; i<G.vexnum; i++) {for (int j=0; j<G.vexnum; j++) {printf("%d ",P[i][j]);}printf("\n");}for (int i=0; i<G.vexnum; i++) {for (int j=0; j<G.vexnum; j++) {printf("%d ",D[i][j]);}printf("\n");}return 0;}