迪克斯特拉算法：单源最短路径问题

一、迪杰斯特拉算法的介绍

迪杰斯特拉（Dijkstra）算法是一种用于计算加权图中单源最短路径的经典算法，由荷兰计算机科学家艾兹赫·迪杰斯特拉（Edsger Dijkstra）于1956年提出。迪杰斯特拉算法的核心思想是通过贪心策略，不断选择当前路径代价最小的节点，并逐步扩展搜索范围，直到找到从源节点到所有可达节点的最短路径。它适用于非负权重的加权图，不能处理负权重。

二、单源最短路径问题的介绍

1.介绍

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和，这个问题通常称为单源最短路径问题。该问题的经典求解方法为迪克斯特拉算法，该算法基于贪心法进行设计，能够有效求解单源最短路径问题。

2.举例

下面这个图片是对单源最短路径进行解释

由这个图片可以看到，由a开始，分别向b,c,d e,f四个顶点进行遍历，查找分别到四个顶点中的最短路径的问题

下面利用迪克斯特拉算法来进行解释：

由a开始有两个顶点可以到达，分别是b和c，他们的权重为2和5，其他三个点都无法到达，则把他们表示为无穷。

由图表可知，得到b开始，可到达c与d，权重分别为3和5，e和f则无法到达。

由c出发，开始向e和f，权重分别为7和4。

由上面的三次可以知道最后的两次遍历情况。

三、算法的代码编写

1.图的表示

 代码使用邻接矩阵来表示图，其中 adjMatrix[i][j] 表示从节点 i 到节点 j 的边的权重。

如果两个节点之间没有直接的边，则初始化为 INT_MAX（无穷大）

#include <stdio.h>
#include <limits.h>
#define MAX_VERTICES 100
struct Graph {
	int numVertices;
	int numEdges;
    int adjMatrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
};
void inputGraph(struct Graph* graph) {
	printf("输入顶点数：");
	scanf("%d", &graph->numVertices);
	printf("输入边数：");
	scanf("%d", &graph->numEdges);
	// 初始化邻接矩阵为无穷大
	
	for (int i = 0; i < graph->numVertices; i++) {
	    for (int j = 0; j < graph->numVertices; j++) {
	        graph->adjMatrix[i][j] = (i == j) ? 0 : INT_MAX; 
	    }
	}

	int u, v, w;
	for (int i = 0; i < graph->numEdges; i++) {
	    printf("输入边 u, v, w（例如：0 1 5 表示从顶点0到顶点1的边权重为5）：");
	    scanf("%d %d %d", &u, &v, &w);
	    graph->adjMatrix[u][v] = w; 
	    
	}
}

2.迪克斯特拉算法的实现

（1）、初始化：dist 数组记录从源节点到每个节点的最短距离，初始时 dist[startVertex] = 0，其他节点 dist[i] = INT_MAX。visited 数组标记节点是否被访问过，初始时所有节点都未被访问（visited[i] = 0）。prev 数组记录从源节点到每个节点的前驱节点，初始时 prev[i] = -1。

（2）、选择当前最短路径的节点：在每一轮迭代中，从未访问的节点中选择 dist[v] 最小的节点 u 进行扩展。

（3）、更新邻居节点的最短路径：遍历 u 的所有邻居节点 v，如果通过 u 到 v 的路径比当前记录的 dist[v] 更短，则更新 dist[v] 和 prev[v]。

void Dijkstra(struct Graph* graph, int startVertex) {
	int dist[MAX_VERTICES]; // 距离数组
    int visited[MAX_VERTICES] = {0}; // 访问数组
	int prev[MAX_VERTICES]; // 顶点数组
	for (int i = 0; i < graph->numVertices; i++) {
	    dist[i] = INT_MAX;
	    prev[i] = -1;
	}
	dist[startVertex] = 0; // 起点到自身的距离为0
	
	for (int count = 0; count < graph->numVertices - 1; count++) {
	    int u = -1; // 距离最小的顶点
	    int minDist = INT_MAX;
	    for (int v = 0; v < graph->numVertices; v++) {
	        if (!visited[v] && dist[v] < minDist) {
	            minDist = dist[v];
	            u = v;
	        }
	    }
	    visited[u] = 1;
	    for (int v = 0; v < graph->numVertices; v++) {
	        if (graph->adjMatrix[u][v] != INT_MAX && !visited[v] && dist[u] + graph->adjMatrix[u][v] < dist[v]) {
	            dist[v] = dist[u] + graph->adjMatrix[u][v];
	            prev[v] = u;
	        }
	    }
	}
	// 打印结果
	printf("从顶点 %d 到其他顶点的最短距离：\n", startVertex);
	for (int i = 0; i < graph->numVertices; i++) {
	    if (dist[i] == INT_MAX) {
	        printf("到顶点 %d 不可达\n", i);
	    } else {
	        printf("到顶点 %d 的距离为 %d\n", i, dist[i]);
	        printf("路径：");
	        int current = i;
	        while (current != -1) {
	            printf("%d ", current);
	            current = prev[current];
	        }
	        printf("\n");
	        
	    }
	}
}

3.路径输出

 printf("到顶点 %d 的距离为 %d\n", i, dist[i]);
	        printf("路径：");
	        int current = i;
	        while (current != -1) {
	            printf("%d ", current);
	            current = prev[current];
	        }
	        printf("\n");
	        

4.输入验证：

int main() {
	struct Graph graph;
	inputGraph(&graph);
	int startVertex;
	printf("输入起点顶点（从0开始编号）：");
	scanf("%d", &startVertex);
	// 验证起点是否在图的顶点范围内
	if (startVertex < 0 || startVertex >= graph.numVertices) {
	    printf("起点顶点编号无效！\n");
	    return 1;
	}
	Dijkstra(&graph, startVertex);
	return 0;
	}

四、单源最短路径问题的应用场

地图导航与路径规划：介绍迪克斯特拉算法在地图导航中的应用，计算从起点到终点的最短路径。

网络路由与数据转发：说明迪克斯特拉算法在计算机网络中的应用，计算最优传输路径。

物流与供应链管理：阐述迪克斯特拉算法在物流管理中的应用，优化运输路线，降低运输成本。

机器人导航与路径规划：介绍迪克斯特拉算法在机器人导航中的应用，计算机器人从起点到终点的最短路径。