广州市 网站建设 有限公司,wordpress 4.0.23漏洞,免费户型设计网站,杭州知名app技术开发公司Dijkstra算法 一、概述二、Dijkstra算法步骤三、相关代码 一、概述 Dijkstra算法是一种用于找到图中最短路径的算法。
二、Dijkstra算法步骤
Dijkstra算法是一种用于求解带权图中单源最短路径的算法。以下是Dijkstra算法的步骤#xff1a; 初始化#xff1a;创建两个数组 初始化创建两个数组一个用于记录每个节点的最短路径长度dist数组初始值为无穷大另一个用于判断节点是否已经被访问visited数组初始值为未访问。 设置起点将起点的最短路径长度设置为0并将其标记为已访问。 更新最短路径对于起点的所有邻接节点计算通过起点到达该节点的路径长度并更新dist数组中的最短路径长度。 选择最短路径节点从未访问的节点中选择一个最短路径长度最小的节点并将其标记为已访问。 更新其它节点的最短路径对于刚被访问的节点的邻接节点计算通过刚被访问的节点到达该邻接节点的路径长度并更新dist数组中的最短路径长度。 重复步骤4和5直到所有节点都被访问。 最短路径获取根据dist数组中的最短路径长度可以得到从起点到其他节点的最短路径。
三、相关代码
下面是用C语言编写的Dijkstra算法的代码示例
#include stdio.h
#include stdbool.h// 定义无穷大的值
#define INFINITE 9999
#define MAX_NODES 10// 计算最短路径
void dijkstra(int graph[MAX_NODES][MAX_NODES], int start, int dist[MAX_NODES], bool visited[MAX_NODES]) {// 初始化dist数组和visited数组for (int i 0; i MAX_NODES; i) {dist[i] INFINITE;visited[i] false;}// 设置起点的最短路径长度为0dist[start] 0;// 寻找最短路径for (int count 0; count MAX_NODES - 1; count) {int minDist INFINITE;int minDistNode -1;// 选择最短路径长度最小的节点for (int i 0; i MAX_NODES; i) {if (!visited[i] dist[i] minDist) {minDist dist[i];minDistNode i;}}// 标记该节点为已访问visited[minDistNode] true;// 更新其他节点的最短路径长度for (int i 0; i MAX_NODES; i) {if (!visited[i] graph[minDistNode][i] dist[minDistNode] ! INFINITE dist[minDistNode] graph[minDistNode][i] dist[i]) {dist[i] dist[minDistNode] graph[minDistNode][i];}}}
}int main() {int graph[MAX_NODES][MAX_NODES] {{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};int start 0;int dist[MAX_NODES];bool visited[MAX_NODES];dijkstra(graph, start, dist, visited);printf(节点\t最短路径长度\n);for (int i 0; i MAX_NODES; i) {printf(%d\t%d\n, i, dist[i]);}return 0;
}以上代码实现了Dijkstra算法的功能可以计算带有权值的图中从起点到其他节点的最短路径长度。输入的图使用邻接矩阵表示其中无连接的两个节点之间的距离为0。输出结果为每个节点的最短路径长度。
