Dijkstra 求最短路

acwing上有位博主的解析非常哈

求源点到其余各点的最短距离步骤如下：

用一个 dist 数组保存源点到其余各个节点的距离，dist[i] 表示源点到节点 i 的距离。初始时，dist 数组的各个元素为无穷大。
用一个状态数组 state 记录是否找到了源点到该节点的最短距离，state[i] 如果为真，则表示找到了源点到节点 i 的最短距离，state[i] 如果为假，则表示源点到节点 i 的最短距离还没有找到。初始时，state 各个元素为假。

源点到源点的距离为 0。即dist[1] = 0。

遍历 dist 数组，找到一个节点，这个节点是：没有确定最短路径的节点中距离源点最近的点。假设该节点编号为 i。此时就找到了源点到该节点的最短距离，state[i] 置为 1。

遍历 i 所有可以到达的节点 j，如果 dist[j] 大于 dist[i] 加上 i -> j 的距离，即 dist[j] > dist[i] + w[i][j]（w[i][j] 为 i -> j 的距离） ，则更新 dist[j] = dist[i] + w[i][j]。

重复 3 4 步骤，直到所有节点的状态都被置为 1。

此时 dist 数组中，就保存了源点到其余各个节点的最短距离。

 题目

给定一个 nn 个点 mm 条边的有向图，图中可能存在重边和自环，所有边权均为正值。

请你求出 11 号点到 nn 号点的最短距离，如果无法从 11 号点走到 nn 号点，则输出 −1−1。

输入格式

第一行包含整数 nn 和 mm。

接下来 mm 行每行包含三个整数 x,y,zx,y,z，表示存在一条从点 xx 到点 yy 的有向边，边长为 zz。

输出格式

输出一个整数，表示 11 号点到 nn 号点的最短距离。

如果路径不存在，则输出 −1−1。

数据范围

1≤n≤5001≤n≤500,
1≤m≤1051≤m≤105,
图中涉及边长均不超过10000。

代码1

 
import java.util.Arrays;
import java.util.Scanner;
 
 
public class Main {
    //从这里看，边是比较多的，所有可以用邻接矩阵存数据
 
    static int N = 510;
    static int m, n;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
 
    //注意：有向图和无向图相比，无向图可以看出有向图
    //如果有重边，保留距离最短的那条边
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); m = sc.nextInt();
 
        for (int i = 1; i <= n; i++) Arrays.fill(g[i], 0x3f3f); //权值不超过10000
        while (m-- > 0) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            g[a][b] = Math.min(g[a][b], c);
        }
 
        // 表示1号点到n号点的最短距离
        System.out.println(dijkstra());
    }
 
    private static int dijkstra() {
        Arrays.fill(dist, 0x3f3f);
 
        dist[1] = 0; //把自己的距离设置为 0
 
        //遍历一遍 找到一个最小的点，加入到集合中，这里加入到集合里，是通过st来做
 
        //迭代n次，n次迭代后获得最终结果集
        for (int i = 0; i < n; i++) {
            int t = -1; //表示还没有最短的点
            for (int j = 1; j <= n; j++) {
                if (!st[j] && (t == -1 || dist[t] > dist[j])) {
                    t = j;
                }
            } //循环后找到了最短的点，为 t
 
            st[t] = true; // t 加进结果集中
 
            //最后拿 t 更新一下结果集
            for (int j = 1; j <= n; j++) dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
        }
 
        if (dist[n] == 0x3f3f) return -1;
        else return dist[n];
    }
}
 

代码2

#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个点所以要进行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()<
    return 0;
}