保定网站免费制作,私人网站制作 个人使用,最新网站发布,金华网站建设方案咨询简介
迪杰斯特拉#xff08;Dijkstra#xff09;算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它是由荷兰计算机科学家艾兹格迪科斯彻#xff08;Edsger Dijkstra#xff09;在1956年提出的。Dijkstra算法适用于处理带有非负权重的图。迪杰斯特拉…简介
迪杰斯特拉Dijkstra算法是一种用于在加权图中找到单个源点到所有其他顶点的最短路径的算法。它是由荷兰计算机科学家艾兹格·迪科斯彻Edsger Dijkstra在1956年提出的。Dijkstra算法适用于处理带有非负权重的图。迪杰斯特拉算法主要特点是从起始点开始采用贪心算法每次遍历到始点距离最近且未访问过的顶点的邻接节点直到扩展到终点为止。适用的是单源路径最短路问题对于多源则采用弗洛伊德Floyd算法
Dijkstra算法原理 初始化 创建一个距离数组dist用来存储从起始节点到每个节点的最短距离初始时将起始节点的距离设为0其余节点设为无穷大。创建一个优先队列通常使用最小堆来存储待处理的节点初始时将起始节点加入队列。 处理节点 从优先队列中取出距离最小的节点标记为已处理。对于该节点的每个邻接节点计算从起始节点到该邻接节点的距离。如果这个距离小于当前记录的距离则更新距离并将该邻接节点加入优先队列。 重复 重复步骤2直到优先队列为空或者所有节点都被处理。
如果还看不明白,请看下图 举个栗子
示例图 图的邻接表表示
节点0到节点1的边权重为1节点0到节点2的边权重为4节点1到节点2的边权重为2节点1到节点3的边权重为5节点2到节点4的边权重为1节点4到节点3的边权重为1
Dijkstra算法执行过程
假设我们从节点0开始以下是dist和visited数组在每一步的变化 初始化 dist [0, ∞, ∞, ∞, ∞] 从起始节点0到其他节点的距离visited [false, false, false, false, false] 所有节点未被访问 处理节点0 当前节点0更新邻接节点1和2 dist[1] 10到1的距离dist[2] 40到2的距离更新后的数组 dist [0, 1, 4, ∞, ∞]visited [true, false, false, false, false] 处理节点1下一个最小距离的节点 当前节点1更新邻接节点2和3 dist[2] min(4, 1 2) 3更新0到2的距离dist[3] 1 5 6更新0到3的距离更新后的数组 dist [0, 1, 3, 6, ∞]visited [true, true, false, false, false] 处理节点2 当前节点2更新邻接节点4 dist[4] min(∞, 3 1) 4更新0到4的距离更新后的数组 dist [0, 1, 3, 6, 4]visited [true, true, true, false, false] 处理节点4 当前节点4更新邻接节点3 dist[3] min(6, 4 1) 5更新0到3的距离更新后的数组 dist [0, 1, 3, 5, 4]visited [true, true, true, false, true] 处理节点3 当前节点3由于3没有未访问的邻接节点算法结束。最终的dist数组为 dist [0, 1, 3, 5, 4]从节点0到各个节点的最短距离visited数组为 visited [true, true, true, true, true]所有节点均已访问
最终结果
从节点0到节点1的最短距离是1从节点0到节点2的最短距离是3从节点0到节点3的最短距离是5从节点0到节点4的最短距离是4
这个过程展示了Dijkstra算法如何逐步更新每个节点的最短路径并标记已访问的节点。
代码实现
#includeiostream
using namespace std;
int n,e,s;//n个顶点e条边s是起点
int dis[101];//dis[i]起点到i的最短距离
int vis[101];//标记是否找到
int edge[101][101];//记录路径i-j有路径
int main()
{cinne;for(int i1;in;i){dis[i]100000;}for(int i1;ie;i){//邻接矩阵存储int a,b,c;cinabc;edge[a][b]c;}cins;dis[s]0;//起点到起点不需要代价for(int i1;in;i){int minninf,minx;for(int j1;jn;j){if(dis[j]minnvis[j]0){//寻找此点到其他点的最小距离minndis[j];minxj;}}vis[minx]1;//标记到达的最小点for(int j1;jn;j){if(edge[minx][j]0)//有边的话 {if(minnedge[minx][j]dis[j]){dis[j]minnedge[minx][j];//更新以最小距离点最为中转点的最小距离}}}}for(int i1;in;i){//打印最短距离coutdis[i] ;}return 0;
}
