Dijkstra整体思路

该算法的真题思路比较清晰，即进行n（n 为 n 个数）次迭代去确定每个点到起点的最小值，最后输出的终点即为我们要找的最短距离。
总之，我们按照这个思路除了存储图以外，我们还需要存储两个量。

int dist[n] //用于存储每个点到起点的最短距离
bool st[n] //用于在更新最短距离时判断当前的点的最短距离是否正确，是否需要更新

每次迭代的过程中我们都线找到当前未确定的最短距离的点中，距离最短的呢个点。
（至于为什么是这样那么这就涉及到Dijkstra算法的具体数学证明了 有兴趣的同学可以百度一下）

int t = -1;
for (int i = 0; i < n ; i++ )
{
if (! st[j] && (t == -1 || dist[t] > dist[j]) t = j;
}

通过上述的操作当前我们的 t 代表就是剩余的未确定的最短路的点中，路径最短的点。
而于此同时，该点的最短路径也已经确定，因此我们该对该店进行标记

st[t] = true;

然后用这个去更新其余未确定点的最短距离。

for (int j = 1; j <= n; j++)
dist[j] = min (dist[j],dist[t] + g[t][j]);
//这里可能有同学要问j如果从1开始的话 会不会影响之前已经确定的点的最小距离
//但其实是不会 因为按照我们的Dijkstra算法的操作顺序 先确定最短距离的点的距离已经比后确定的要小 所以不会影响
//当然你也可以在循环判断条件里加上if(!st[i])
//这里j从1开始只是为了代码的简洁

进行n次迭代后最后就可以确定每个点的最短距离
然后再根据题意输出相应的 要求的最短距离

代码实现

具体落实到代码，我们通过一道题来进一步去理解

代码实现

#include
#include
#include
using namespace std;

const int N=510;

int g[N][N];    //为稠密阵所以用邻接矩阵存储
int dist[N];    //用于记录每一个点距离第一个点的距离
bool st[N];     //用于记录该点的最短距离是否已经确定

int n,m;

int Dijkstra()
{
    memset(dist, 0x3f,sizeof dist);     //初始化距离  0x3f代表无限大

    dist[1]=0;  //第一个点到自身的距离为0

    for(int i=0;i<n;i++)      //有n个点所以要进行n次 迭代
    {
        int t=-1;       //t存储当前访问的点

        for(int j=1;j<=n;j++)   //这里的j代表的是从1号点开始
            if(!st[j]&&(t==-1||dist[t]>dist[j]))     
                t=j;

        st[t]=true;   

        for(int j=1;j<=n;j++)           //依次更新每个点所到相邻的点路径值
            dist[j]=min(dist[j],dist[t]+g[t][j]);
    }

    if(dist[n]==0x3f3f3f3f) return -1;  //如果第n个点路径为无穷大即不存在最低路径
    return dist[n];
}
int main()
{
    cin>>n>>m;

    memset(g,0x3f,sizeof g);    //初始化图 因为是求最短路径
                                //所以每个点初始为无限大

    while(m--)
    {
        int x,y,z;
        cin>>x>>y>>z;
        g[x][y]=min(g[x][y],z);     //如果发生重边的情况则保留最短的一条边
    }

    cout<<Dijkstra()<<endl;
    return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56