当前位置：首页 > news >正文

C语言-数据结构无向图迪杰斯特拉算法(Dijkstra)邻接矩阵存储

news 来源：原创 2024/9/20 13:48:56

在迪杰斯特拉中，相比普利姆算法，是从顶点出发的一条路径不断的寻找最短路径，在实现的时候需要创建三个辅助数组，记录算法的关键操作，分别是Visited[MAXVEX]记录顶点是否被访问，教材上写的final数组但作用是一样的，然后第二个数组是TmpDistance[MAXVEX]，教材使用的D数组，命名语义化较弱不太好理解，实际用途与TmpDistance一样的，用于记录算法过程中，当前顶点到达邻接顶点的最小值，Path[MAXVEX]用于记录每个顶点的前驱结点，通过它可以记录到达所有顶点路径的路线，非常巧妙！整个算法过程非常像一只长了触角的贪吃蛇，用最短的身长到达所有顶点，触手想象成每次循环中探索最短邻接顶点的操作。

我们将创建下面的无向权值图：

邻接矩阵的绘制还是手动赋值上三角，并通过矩阵对称性生成整个邻接矩阵，其中最小生成树中需要用到权值，对应原本有边的地方之前我是用1表示，现在改成边对应的权值，之前的0表示没有边，现在改成99表示为无穷，其实应该换成更大的值以确保树的边权值都小于这个最大值，但为了方便对齐显示看邻接矩阵，就使用了比本图中各边长较大的99来表示最大值。

Dijkstra算法代码

//v0起点,path路径,d临时辅助最短路径数组
void Dijkstra(MGraph G, int Vstart,int TmpDistance[],int Path[]) {int v, w, UpcomingVex, min;int Visited[MAXVEX];//初始化所有顶点for (v = 0; v < G.numNodes; v++) {Visited[v] = FALSE;TmpDistance[v] = G.arc[Vstart][v];Path[v] = -1;}//起始点路径长度为0TmpDistance[Vstart] = 0;//起始点标记为已经被访问Visited[Vstart] = TRUE;//遍历所有顶点,总计遍历n-1次所以，主循环控制次数就从1开始，求得当前顶点Vi到达相邻结点的最近距离的顶点，并标记Visited为已经找到for (v = 1; v < G.numNodes; v++) {min = GRAPH_INFINITY; // 初始化最小距离为无穷大// 寻找当前未访问的顶点中距离起始点最近的顶点for (w = 0; w < G.numNodes; w++) {if (!Visited[w] && TmpDistance[w] < min) {UpcomingVex = w;min = TmpDistance[w];}}// 标记找到的顶点为已访问Visited[UpcomingVex] = true;// 更新从当前顶点到其他顶点的最短路径for (w = 0; w < G.numNodes; w++) {if (!Visited[w] && (min + G.arc[UpcomingVex][w] < TmpDistance[w])) {TmpDistance[w] = min + G.arc[UpcomingVex][w];Path[w] = UpcomingVex; // 记录路径}}}
}

打印路径函数，根据Dijkstra算法计算的Path数组进行，Path数组用到了并查集的部分思想，Dijkstra中我们所有顶点都是一个集合，-1表示前驱结点为自身即找到起点，也表示为同一个集合，搜索路径的过程需要一步一步往回查找，用到了并查集中的Find函数，比如A->B->C，我们Path数组是从C顶点出发然后根据path存储的内容找到前驱结点B然后再找到A，我这里为了方便直接用数组存储路径，逆序打印就行，也可以用栈进行存储。

// 打印从起点到各顶点的路径
void PathVexPrint(int Path[]) {for (int start = 0; start < MAXVEX; start++) {int i = start;char tmp[10] = "";int count = 0;// 追踪路径while (i >= 0) {tmp[count++] = 'A' + i; // 假设顶点用字母表示i = Path[i];}tmp[count++] = 'A'; // 添加起始点// 反向输出路径for (int j = count - 1; j >= 0; j--) {printf("%c", tmp[j]);if (j > 0) {printf("->");}}printf("\n");}
}

完整代码（包含邻接矩阵的创建、迪杰斯特拉算法）

#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"// 禁用特定的警告
#pragma warning(disable:4996)// 定义一些常量和数据类型
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 8 /* 最大顶点数，用户定义 */
#define MAXEDGE 10 /* 最大边数，用户定义 */
#define GRAPH_INFINITY 99 /* 用0表示∞，表示不存在边 *//* 定义状态、顶点和边的类型 */
typedef int Status;  /* Status是函数的返回类型，如OK表示成功 */
typedef char VertexType; /* 顶点的类型，用字符表示 */
typedef int EdgeType; /* 边上的权值类型，用整数表示 */
typedef int Boolean; /* 布尔类型 */
// 定义顶点标签
char Array[] = "ABCDEFGHI";/* 图的邻接矩阵结构体 */
typedef struct
{VertexType vexs[MAXVEX]; /* 顶点表 */EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，表示边的权值 */int numNodes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;/* 创建一个无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{int i, j, k, w;// 初始化图的顶点数和边数G->numNodes = 8;G->numEdges = 10;// 初始化邻接矩阵和顶点表for (i = 0; i < G->numNodes; i++) {for (j = 0; j < G->numNodes; j++) {G->arc[i][j] = GRAPH_INFINITY; /* 初始化邻接矩阵为∞ */}G->vexs[i] = Array[i]; /* 初始化顶点表 */}G->arc[0][0] = GRAPH_INFINITY;G->arc[0][1] = 10;G->arc[0][2] = GRAPH_INFINITY;G->arc[0][3] = GRAPH_INFINITY;G->arc[0][4] = GRAPH_INFINITY;G->arc[0][5] = 11;G->arc[0][6] = GRAPH_INFINITY;G->arc[0][7] = GRAPH_INFINITY;G->arc[1][0] = GRAPH_INFINITY;G->arc[1][1] = GRAPH_INFINITY;G->arc[1][2] = 23;G->arc[1][3] = GRAPH_INFINITY;G->arc[1][4] = GRAPH_INFINITY;G->arc[1][5] = GRAPH_INFINITY;G->arc[1][6] = 12;G->arc[1][7] = GRAPH_INFINITY;G->arc[2][0] = GRAPH_INFINITY;G->arc[2][1] = GRAPH_INFINITY;G->arc[2][2] = GRAPH_INFINITY;G->arc[2][3] = 21;G->arc[2][4] = GRAPH_INFINITY;G->arc[2][5] = GRAPH_INFINITY;G->arc[2][6] = GRAPH_INFINITY;G->arc[2][7] = GRAPH_INFINITY;G->arc[3][0] = GRAPH_INFINITY;G->arc[3][1] = GRAPH_INFINITY;G->arc[3][2] = GRAPH_INFINITY;G->arc[3][3] = GRAPH_INFINITY;G->arc[3][4] = GRAPH_INFINITY;G->arc[3][5] = GRAPH_INFINITY;G->arc[3][6] = GRAPH_INFINITY;G->arc[3][7] = 11;G->arc[4][0] = GRAPH_INFINITY;G->arc[4][1] = GRAPH_INFINITY;G->arc[4][2] = GRAPH_INFINITY;G->arc[4][3] = GRAPH_INFINITY;G->arc[4][4] = GRAPH_INFINITY;G->arc[4][5] = 47;G->arc[4][6] = GRAPH_INFINITY;G->arc[4][7] = 80;G->arc[5][0] = GRAPH_INFINITY;G->arc[5][1] = GRAPH_INFINITY;G->arc[5][2] = GRAPH_INFINITY;G->arc[5][3] = GRAPH_INFINITY;G->arc[5][4] = GRAPH_INFINITY;G->arc[5][5] = GRAPH_INFINITY;G->arc[5][6] = 6;G->arc[5][7] = GRAPH_INFINITY;G->arc[6][0] = GRAPH_INFINITY;G->arc[6][1] = GRAPH_INFINITY;G->arc[6][2] = GRAPH_INFINITY;G->arc[6][3] = GRAPH_INFINITY;G->arc[6][4] = GRAPH_INFINITY;G->arc[6][5] = GRAPH_INFINITY;G->arc[6][6] = GRAPH_INFINITY;G->arc[6][7] = 8;G->arc[7][0] = GRAPH_INFINITY;G->arc[7][1] = GRAPH_INFINITY;G->arc[7][2] = GRAPH_INFINITY;G->arc[7][3] = GRAPH_INFINITY;G->arc[7][4] = GRAPH_INFINITY;G->arc[7][5] = GRAPH_INFINITY;G->arc[7][6] = GRAPH_INFINITY;G->arc[7][7] = GRAPH_INFINITY;// 由于是无向图，邻接矩阵是对称的，需要将其对称for (int i = 0; i < G->numNodes; i++) {for (int j = 0; j < G->numNodes; j++) {G->arc[j][i] = G->arc[i][j];}}// 打印邻接矩阵printf("邻接矩阵为：\n");printf("     ");for (int i = 0; i < G->numNodes; i++) {printf("%2d ", i); /* 打印列索引 */}printf("\n     ");for (int i = 0; i < G->numNodes; i++) {printf("%2c ", G->vexs[i]); /* 打印顶点标签 */}printf("\n");for (int i = 0; i < G->numNodes; i++) {printf("%2d", i); /* 打印行索引 */printf("%2c ", G->vexs[i]); /* 打印顶点标签 */for (int j = 0; j < G->numNodes; j++) {if (G->arc[i][j] != 99) {printf("\033[31m%02d \033[0m", G->arc[i][j]); /* 打印邻接矩阵中的权值 */}else {printf("%02d ", G->arc[i][j]); /* 打印邻接矩阵中的权值 */}}printf("\n");}
}//v0起点,path路径,d临时辅助最短路径数组
void Dijkstra(MGraph G, int Vstart,int TmpDistance[],int Path[]) {int v, w, UpcomingVex, min;int Visited[MAXVEX];//初始化所有顶点for (v = 0; v < G.numNodes; v++) {Visited[v] = FALSE;TmpDistance[v] = G.arc[Vstart][v];Path[v] = -1;}//起始点路径长度为0TmpDistance[Vstart] = 0;//起始点标记为已经被访问Visited[Vstart] = TRUE;//遍历所有顶点,总计遍历n-1次所以，主循环控制次数就从1开始，求得当前顶点Vi到达相邻结点的最近距离的顶点，并标记Visited为已经找到for (v = 1; v < G.numNodes; v++) {min = GRAPH_INFINITY; // 初始化最小距离为无穷大// 寻找当前未访问的顶点中距离起始点最近的顶点for (w = 0; w < G.numNodes; w++) {if (!Visited[w] && TmpDistance[w] < min) {UpcomingVex = w;min = TmpDistance[w];}}// 标记找到的顶点为已访问Visited[UpcomingVex] = true;// 更新从当前顶点到其他顶点的最短路径for (w = 0; w < G.numNodes; w++) {if (!Visited[w] && (min + G.arc[UpcomingVex][w] < TmpDistance[w])) {TmpDistance[w] = min + G.arc[UpcomingVex][w];Path[w] = UpcomingVex; // 记录路径}}}
}
// 打印从起点到各顶点的路径
void PathVexPrint(int Path[]) {for (int start = 0; start < MAXVEX; start++) {int i = start;char tmp[10] = "";int count = 0;// 追踪路径while (i >= 0) {tmp[count++] = 'A' + i; // 假设顶点用字母表示i = Path[i];}tmp[count++] = 'A'; // 添加起始点// 反向输出路径for (int j = count - 1; j >= 0; j--) {printf("%c", tmp[j]);if (j > 0) {printf("->");}}printf("\n");}
}// 打印数组内容
void InfoPrint(int info[]) {printf("\n");for (int i = 0; i < MAXVEX; i++) {printf("%d ", info[i]);}printf("\n");
}
int main(void)
{MGraph G;/* 创建图 */CreateMGraph(&G);int TmpDistance[MAXVEX],Path[MAXVEX];Dijkstra(G, 0, TmpDistance,Path);printf("到达各顶点最短路径的长度(TmpDistance数组)为:\n");printf("A  B  C  D  E  F  G  H  ");InfoPrint(TmpDistance);printf("Path的值为:");InfoPrint(Path);printf("A顶点出发到达各顶点的路径如下：\n");PathVexPrint(Path);return 0;
}

无向图示意图：

运行结果：