Dijkstral-最短路径学习

dijkstral算法在离散这门课中有简单提到过（疯狂吐槽离散老师JY）,但是代码实现一直到之前才学到手，感觉自己还是太傻了摸鱼太严重了。首先建立图的邻接矩阵，对它进行初始化，对角线赋0，其他一律INF。然后输入数据，因为下面代码建立的是无向图，所以在输入的时候要注意以下。建立一个dis数组，初始化为1这个点直接到其它点的距离，建立一个mark数组用来记录是否已经访问过，之后就开始求最短路啦。

下面贴上代码，具体操作代码里面有注释

 1 #include <bits/stdc++.h>
 2 #define fi first
 3 #define se second
 4 #define ll long long
 5 #define db double
 6 const int N=1e5+5;
 7 const int INF=0x3f3f3f3f;
 8 using namespace std;
 9 int a[1005][1005];//邻接矩阵
10 int dis[1005];//存1到各个点的距离，不可达为inf
11 int mark[1005];//是否已访问
12 int main()
13 {
14     int n,m;
15     while(cin>>n>>m)
16     {
17         memset(a,0,sizeof(a));
18         memset(dis,0,sizeof(dis));
19         memset(mark,0,sizeof(mark));
20         if(!n&&!m) break;
21         for (int i=1;i<=n;i++)//初始化
22         {
23             for (int j=1;j<=n;j++)
24             {
25                 if(i==j) a[i][j]=0;
26                 else a[i][j]=INF;
27             }
28         }
29 
30 
31         for (int i=1;i<=m;i++)
32         {
33             int b,c,d;
34             cin>>b>>c>>d;
35             a[b][c]=d;
36             a[c][b]=d;
37         }
38 
39 
40         for(int i=1;i<=n;i++)
41             dis[i]=a[1][i];
42 
43         mark[1]=1;
44         //开始求最短路
45         int index;//记录离第一个点最近的点的下标
46         for (int i=1;i<=n-1;i++)
47         {
48             int minn=INF;
49             for (int j=1;j<=n;j++)
50             {
51                 if(!mark[j]&&minn>dis[j])//如果这个点不是最近的
52                 {
53                     minn=dis[j];
54                     index=j;
55                 }
56             }
57             if(minn==INF) break;
58             mark[index]=1;//index这个点已访问
59 
60             for (int j=1;j<=n;j++)//如果找到比直接连更近的路，替换掉
61             {
62                     dis[j]=min(dis[j],minn+a[index][j]);
63             }
64 
65         }
66         cout<<dis[n]<<endl;
67 
68     }
69 }