算法1

朴素dijkstra

blablabla

时间复杂度

参考文献

Java 代码

import java.util.Arrays;
import java.util.Scanner;


class Main {

    static int N = 510;
    static int[][] graph = new int[N][N];
    static int n;
    static int m;
    static boolean[] st=new boolean[N];//是否已经是最短路径上的点
    static int dist[]=new int[N];//记录最短距离
    public static int dijkstra() {
       Arrays.fill(dist,0x3f3f);
       for (int i = 1; i <= n; i++) {
           //dist i 表示 1到i的距离
            dist[i] = graph[1][i];
        }

        //更新初始节点
        dist[1]=0;
        st[1]=true;
        for(int i=1;i<=n-1;i++){
            int t=-1;//下一个最短路径上的点的序号
            for(int j=1;j<=n;j++){
                if(!st[j]&&(t==-1||dist[j]<dist[t])){
                    t=j;//如果 遍历1-n的节点，如果j没有被访问，并且dist j < dist t;则把j作为确定的最短路径上面的点
                }
            }
            st[t]=true;//把t加入s集合
            //更新距离,点t到其他点的距离
            for(int j=1;j<=n;j++){
                //j 必须要没有在s集合里面！！
                if(!st[j]){
                    dist[j]=Math.min(dist[j],dist[t]+graph[t][j]);
                }
            }
        }
        if (dist[n] == 0x3f3f) return -1;
        return dist[n];
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); // n个顶点
        m = sc.nextInt();
        // 邻接矩阵存储图
        for (int i = 1; i <= n; i++) {
            // 将不存在的边置为  将0x3f3f看成正无穷
            Arrays.fill(graph[i], 0x3f3f);
        }
        for (int i = 0; i <= m-1; i++) {
            int satrt = sc.nextInt();
            int end = sc.nextInt();
            int value = sc.nextInt();
            // 由于存在重边，所以取其最小值
            graph[satrt][end] = Math.min(value,  graph[satrt][end]);
        }

        int res = dijkstra();
        System.out.print(res);
    }


}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla