图论中求最短距离是一个很经典也很重要的问题。本文将从基础概念出发逐步介绍 Dijkstra 这种常用的最短路径算法并结合实际场景分析它们的适用条件与优缺点帮助读者建立起清晰的知识框架。Dijkstra 算法常用于求起点到其他任一点的最短距离。还是先来看一道求最短时间的问题。743. 网络延迟时间 - 力扣LeetCode这道题就是先求起点到每个点的最短距离之后统计最大值。对于图的存储我选择的是邻接矩阵下面是初始化以及加边注意是单向边同时可能有重边这时候优先选权值小的边。int edges[101][101]; void inintedges(int n){ for(int i1;in;i){ for(int j1;jn;j){ edges[i][j]inf; } } } void addedges(int u,int v,int w){ if(edges[u][v]inf||edges[u][v]w) edges[u][v]w; }这是基础工作下面来逐步学习dijkstra算法具体流程是先找到起点之后更新起点到达其他点的距离不能到达距离就是无限大之后遍历其他点找能到达的最小点将这个点加入到树上更新起点到达其他点的距离再找最小距离的点点没找到就说明找完了或者有孤立点下面来看代码先用一个dist数组表示起点到其他点的最短距离并将起点距离标记为零int dist[101]; void initdist(int n,int k){ for(int i1;in;i){ dist[i]inf; } dist[k]0; }注意这里要用到一个visit数组标记已经在树上的点int findmin(int n,int visit[] ){ int u-1,minf; for(int i1;in;i){ if(visit[i]) continue; if(dist[i]m){ mdist[i]; ui; } } return u; } void updata(int n,int u,int visit[]){ visit[u]1; for(int i1;in;i){ if(edges[u][i]inf) continue; if(dist[i]dist[u]edges[u][i]) dist[i]dist[u]edges[u][i]; } } void dijkstra(int n){ int visit[101]; for(int i1;in;i){ visit[i]0; } while(1){ int ufindmin(n,visit); if(u-1){ break; } updata(n,u,visit); } }