彻底理解Dij算法

大家好，欢迎来到IT知识分享网。

1. 理解什么是dij
   简单来说，就是求最短路的一种算法
   
2. 理解dij的核心思想
   百度给出：以起始点为中心向外层层扩展，直到扩展到终点为止
   可咋理解这句话呢？层层扩展，咋扩展？什么是层？
   别急，且听我一一道来：
   1.dij以节点距源点的远近为依据，将其分为一层一层，一个节点便是一层
   2.我们来看其流程：
   a.首先找出距源点S最近的节点A，搜索A的所有出点，判断能否通过SA使S到A的出点的距离减小，能则松弛，当A的所有出点搜索完后，该层扩展完毕
   b. 找出距源点S次近的节点B，搜索B的所有出点，判断能否通过SB使S到B的出点的距离减小，能则松弛，当B的所有出点搜索完后，该层扩展完毕
   c.之后的点依次这样扩展，当扩展到终点时，算法结束
   
   
   
   
   
   
   
   
3. 算法实现

#include <stdio.h> #define inf 0xfffffff #define MAXN 200 int n; int mpt[MAXN][MAXN]; int dis[MAXN]; int vis[MAXN]; int dij(int s,int e)//通过近的点松弛远的点 { int i,j; for(i=1;i<=n;i++)//初始化节点 { dis[i]=mpt[s][i];//也可初始化为inf，不过下面的vis[s]=1必须去掉 vis[i]=0; } dis[s]=0; vis[s]=1; for(i=1;i<=n;i++)//最多松弛n次 { int min=inf,t=0; for(j=1;j<=n;j++)//找出距源点最近的且未访问的点 if(vis[j]==0&&dis[j]<min) min=dis[t=j]; if(min==inf) break;//松弛完毕，退出 vis[t]=1; for(j=1;j<=n;j++)//松弛 if(vis[j]==0&&dis[j]>dis[t]+mpt[t][j])//标记过的点都是比当前点近的点，通过当前点不能松弛比它更接近源点的点 dis[j]=dis[t]+mpt[t][j]; } return (dis[e]==inf)?-1:dis[e]; } int main() { int i,j; while(scanf("%d",&n)!=EOF&&n!=-1) { memset(mpt,1,sizeof(mpt));//图初始化,1表示字节数，视情况而定 //存图 int ans=dij(s,e); printf("%d\n",ans); } return 0; }