企业官网建设流程全解析

图论中求最短距离是一个很经典也很重要的问题。本文将从基础概念出发，逐步介绍 Dijkstra 这种常用的最短路径算法，并结合实际场景分析它们的适用条件与优缺点，帮助读者建立起清晰的知识框架。

Dijkstra 算法常用于求起点到其他任一点的最短距离。

还是先来看一道求最短时间的问题。

743. 网络延迟时间 - 力扣（LeetCode）

这道题就是先求起点到每个点的最短距离，之后统计最大值。

对于图的存储我选择的是邻接矩阵，下面是初始化以及加边（注意是单向边，同时可能有重边，这时候优先选权值小的边）。

int edges[101][101]; void inintedges(int n){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;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 i=1;i<=n;i++){ dist[i]=inf; } dist[k]=0; }

注意这里要用到一个visit数组，标记已经在树上的点

int findmin(int n,int visit[] ){ int u=-1,m=inf; for(int i=1;i<=n;i++){ if(visit[i]) continue; if(dist[i]<m){ m=dist[i]; u=i; } } return u; } void updata(int n,int u,int visit[]){ visit[u]=1; for(int i=1;i<=n;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 i=1;i<=n;i++){ visit[i]=0; } while(1){ int u=findmin(n,visit); if(u==-1){ break; } updata(n,u,visit); } }