单源最短路径问题

无向图【可以转化为BFS扩散问题】

首先先构造邻接表
特殊情况如下：

# 由于是无向图：我们最后要从 2 出发开始扩散
如果不考虑2次的话，就得不到下面的邻接表了，因为是无向图，那么 5 2 也是 2 5，所以我们利用 hashSet来进行操作
5 5
2 1
2 3
2 4
5 2
5 3
2

import java.util.Scanner;
import java.util.*;


// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
   static Map<Integer, Set<Integer>> map = new HashMap<>();   //  邻接表
    static Deque<Integer> deque = new ArrayDeque<>();
    static boolean[] isVisited;
    static int res = 0;

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int count = in.nextInt();   //  点个数
        isVisited = new boolean[count + 1];
        int row = in.nextInt();
        for (int i = 0; i < row; i++) {
            int a = in.nextInt();
            int b = in.nextInt();
            Set<Integer> orDefault1 = map.getOrDefault(a, new HashSet<>());
            orDefault1.add(b);
            Set<Integer> orDefault2 = map.getOrDefault(b, new HashSet<>());
            orDefault2.add(a);
            map.put(a, orDefault1);
            map.put(b, orDefault2);
        }
        int start = in.nextInt();
        deque.offer(start); //  将 2 压入队列
        isVisited[start] = true;
        bfs();
        System.out.println((res - 1) * 2);  //  经过多少天可以辐射全部！！！【减去初始的那天！！！】
    }
  public static void bfs(){
        while (!deque.isEmpty()){
            int len = deque.size();
            while (len > 0){
                Integer peek = deque.pop();
                if (map.containsKey(peek)){
                    Set<Integer> set = map.get(peek);
                    for (Integer integer : set) {
                        if (!isVisited[integer]){
                            deque.offer(integer);
                            isVisited[integer] = true;
                        }
                    }
                }
                len--;
            }
            res++;
        }
    }
}

有向图【Dijistra】