算法分析

题目是一道很裸的单源最短路问题，n = 2500，m = 6200

• 朴素版Dijkstra 复杂度是$O(n^2)$ $n^2 = 6.25 * 10^6$

• 堆优化版dijkstra 复杂度是$O(mlogn)$ $mlogn = 7.44 * 10^4$

• spfa 复杂度是$O(m)$ 平均是2到3倍即 $3 * m = 1.8 * 10^4 $

下面是选用spfa算法

时间复杂度 $O(m)$

最坏$O(mn)$

参考文献

算法提高课

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main{
    static int N = 2510 ;
    static int M = 6200 * 2 + 10;
    static int n;
    static int m;
    static int INF = 0x3f3f3f3f;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static int[] w = new int[M];
    static int idx = 0;
    static void add(int a,int b,int c)
    {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    static int spfa(int start,int end)
    {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        Arrays.fill(dist, INF);
        dist[start] = 0;
        st[start] = true;

        while(!q.isEmpty())
        {
            int t = q.poll();
            st[t] = false;
            for(int i = h[t];i != -1;i = ne[i])
            {
                int j = e[i];
                if(dist[j] > dist[t] + w[i])
                {
                    dist[j] = dist[t] + w[i];
                    if(!st[j])
                    {
                        q.add(j);
                        st[j] = true;
                    }
                }
            }
        }

        return dist[end];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s1 = br.readLine().split(" ");
        n = Integer.parseInt(s1[0]);
        m = Integer.parseInt(s1[1]);
        int start = Integer.parseInt(s1[2]);
        int end = Integer.parseInt(s1[3]);
        Arrays.fill(h, -1);
        while(m -- > 0)
        {
            String[] s2 = br.readLine().split(" ");
            int a = Integer.parseInt(s2[0]);
            int b = Integer.parseInt(s2[1]);
            int c = Integer.parseInt(s2[2]);
            add(a,b,c);
            add(b,a,c);
        }
        System.out.println(spfa(start,end));
    }
}