迪节特斯拉最短路径算法

最短路径求取依靠的是邻接矩阵

从点1出发

依次到其他各点的距离是

无穷大代表无法到达，其中1->2的距离最短 然后查看2到达各点的距离

发现2->4距离为3然后更新1点到各点的距离 依次是0、1、12、1+3、无穷、无穷

然后查点4到达其余个点的距离

然后  其到3点的距离为4，因为1+3+4<12故更新0、1、1+3+4、1+3、无穷、无穷

观察点3到其余各点的距离

到点5距离为5，因此可以更新点1到各点的距离为0、1、1+3+4、1+3、1+3+4+5、无穷

同理观察5点到个点的距离更新点1到各点的距离0、1、1+3+4、1+3、1+3+4+5、1+3+4+5+4

也就是0、1、8、4、13、17

这时点1到其他个点的最短路径也就求得

1-2点直接到达距离为1

1-3点最短路径是1-2-4-3，距离为8

1-4点最短路径是1-2-4，距离为4

1-5点最短路径1-2-4-3-5，距离为13

1-6点最短路径1-2-4-3-5-6，距离为17

代码求解如下

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define Inf 0x3f3f3f3f
 
using namespace std;
 
int map[1005][1005];
 
int vis[1005],dis[1005];
int n,m;//n个点，m条边
 
void Init ()
{
    memset(map,Inf,sizeof(map));
    for(int i=1;i<=n;i++)
    {
        map[i][i]=0;
    }
}
 
void Getmap()
{
    int u,v,w;
    for(int t=1;t<=m;t++)
    {
          scanf("%d%d%d",&u,&v,&w);
          if(map[u][v]>w)
          {
          map[u][v]=w;
          map[v][u]=w;
          }
    }    
    
}
 
void Dijkstra(int u)
{
    memset(vis,0,sizeof(vis));
    for(int t=1;t<=n;t++)
    {
        dis[t]=map[u][t];
    }
    vis[u]=1;
    for(int t=1;t<n;t++)
    {
        int minn=Inf,temp;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i]&&dis[i]<minn)
            {
                minn=dis[i];
                temp=i;
            }
        }
        vis[temp]=1;
        for(int i=1;i<=n;i++)
        {
            if(map[temp][i]+dis[temp]<dis[i])
            {
                dis[i]=map[temp][i]+dis[temp];
            }
        }
    }
    
}
 
int main()
{
    
    scanf("%d%d",&m,&n);
    Init();
    Getmap();
    Dijkstra(n);
    printf("%d\n",dis[1]);
    
    
    return 0;
}