单源最短路问题（Dijkstra算法）

单源最短路问题

单元最短路定义：从起点到其它每一个点的最短距离
思路：
每次用上一次已经确定的点的最短距离来更新该次每个点的最短距离。
下面举个例子来说明：

5 7
1 2 1
2 3 2
1 3 2
1 4 3
2 5 6
3 4 4
4 5 1
1
2
3
4
5
6
7
8

重点理解：每一次更新都是上一次更新出来的最小值加上这次的值
上代码

#include<bits/stdc++.h>
using namespace std;
const int N = 510;
int n,m;
int g[N][N];
bool st[N];
int dist[N];

int Dijkstram()
{
    dist[1] = 0;//第一个点到起点的距离为0
    
    for(int i=0;i<n-1;i++)//更新n-1次
    {
        int t = -1;//用来更新每次确定的点。然后用这个确定的点更新每一个的最小值。
        
        for(int j = 1 ; j<=n ; j++)
            if(!st[j] && (t =&#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17