C/C++提高篇

2023-12-01 07:07| 来源: 网络整理| 查看: 265

名人说：一花独放不是春，百花齐放花满园。——《增广贤文》作者：Code_流苏(CSDN)（一个喜欢古诗词和编程的Coder😊）

目录〇、Dijkstra迪杰斯特拉算法介绍1、Dijkstra算法是什么？2、Dijkstra算法的由来3、Dijkstra算法的基本思想一、代码及注释二、思路阐明三、样例测试

以下代码个人分享出来，仅供学习交流，且仅在CSDN平台发布，未经授权禁止二次转发。

〇、Dijkstra迪杰斯特拉算法介绍 1、Dijkstra算法是什么？

Dijkstra算法是一个基于「贪心」、「广度优先搜索」、「动态规划」求一个图中一个点到其他所有点的最短路径的算法，常规迪杰斯特拉算法的时间复杂度 O (n^2) 。

2、Dijkstra算法的由来

它是由荷兰计算机科学家艾茲赫尔·戴克斯特拉在1956年发现的，并于3年后在期刊上发表。

在这里插入图片描述他的一些学术贡献包括（但不仅限于）：

提出了目前在离散数学中应用广泛的最短路径算法（Dijkstra’s Shortest Path First Algorithm）为解决操作系统中资源分配问题，提出银行家算法。

又是膜拜大佬的一天

3、Dijkstra算法的基本思想首先，将所有的顶点分为两个集合：已经求出最短路径的顶点集合（用S表示）和未求出最短路径的顶点集合（用Q表示）。初始时，S只包含源点，Q包含除源点外的其他顶点，源点到自身的距离为0，源点到其他顶点的距离为无穷大（或者是邻接矩阵中对应的权值）。然后，每次从Q中选择一个距离最小的顶点u，将其加入到S中，并用u更新Q中的其他顶点的距离，即如果存在一条从u到v的边，且dist[u]+w(u,v) int v;//边的终止顶点 int w;//边的权值 }Edge; typedef struct//图的结构体 { VertexType vex[MAXV];//顶点表 vector arcs[MAXV];//邻接表 int vexnum,arcnum;//顶点数目和边的数目 }AMGraph; void CreateGraph(AMGraph *G)//创建图 { int i; int u,v,w; coutG->vexnum>>G->arcnum; cout G->vex[i].no=i; cout>w; G->arcs[u].push_back({v,w}); //添加边到邻接表 G->arcs[v].push_back({u,w}); //无向图需要添加两次 } } void Dispath(AMGraph G,int dist[],int path[],int s[],int v)//输出 { int i,j,k; int apath[MAXV],d;//存放一条最短路径及其顶点个数 for(i=0;i while(k!=v) { d++;apath[d]=k; k=path[k]; } d++;apath[d]=v;//添加路径上的起点 cout dist[i]=INF;//距离初始化为无穷大 s[i]=0;//s[]置空 path[i]=-1;//路径初始化为-1 } dist[v]=0;//源点到自身的距离为0 q.push({0,v});//源点入队 while(!q.empty())//队列不为空时循环 { u=q.top().second;//取出队首的顶点 q.pop();//出队 if(s[u]==1) continue;//如果已经加入最短路径顶点集，跳过 s[u]=1;//否则，将其加入最短路径顶点集 for(auto e:G.arcs[u])//遍历u的邻接边 if(s[e.v]==0)//如果终点不在s中 if(dist[u]+e.wdist[e.v],e.v});//将终点入队 } } Dispath(G,dist,path,s,v);//输出 } int main() { AMGraph G; CreateGraph(&G); Dijkstra(G,0); return 0; } 二、思路阐明

① 首先，创建一个图的结构体，用顶点表和邻接表来存储图的信息，顶点表中存储顶点的编号和名字，邻接表中存储每个顶点的邻接边和权值。

② 然后，输入顶点数和边数，以及每个顶点的名字和每条边的起点、终点和权值，将它们添加到图的结构体中。

③ 接着，定义一个dist数组，用来存储源点到其他顶点的最短距离，初始化为无穷大；定义一个path数组，用来存储到达终点前的最后一个顶点，初始化为-1；定义一个s数组，用来标记是否加入最短路径顶点集，初始化为0；定义一个优先队列，用来存储未加入最短路径顶点集的顶点，并按照距离从小到大排序。

④ 然后，将源点到自身的距离设为0，并将源点入队。

⑤ 接着，循环直到队列为空，每次取出队首的顶点u，并将其加入最短路径顶点集。然后遍历u的邻接边，如果终点v不在最短路径顶点集中，并且dist[u]+w

【本文地址】

公司简介

联系我们

今日新闻

推荐新闻

专题文章