单源最短路

朴素Dijkstra算法

有n个结点，从1到n。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 构建邻接矩阵
g := make([][]int, n + 1)
   
   for i := range g{
       g[i] = make([]int, n + 1)
   }
   
   for i := 1; i <= n; i++ {
       for j := 1; j <= n; j++ {
           if i == j {
               g[i][j] = 0
           }else{
               g[i][j] = math.MaxInt32 / 2
           }
       }
   }
   
   //Dijkstra算法
   s :=  make([]bool, n + 1) //表示点是否已经加入集合
   dist := make([]int, n + 1) //从源点到各个点的距离
   
   //将1作为起点，其余各点距离为无穷大
   dist[1] = 0
   for i := 2; i <= n; i++{
       dist[i] = math.MaxInt32
   }
   
   for i := 0; i < n ; i++{ //将n个点加入集合s中
       t := -1
       for j := 1; j <= n; j++{ //找到没在集合中的点
           if !s[j] && (t == -1 || dist[t] > dist[j]){
               t = j
           }
       }
       
       s[t] = true //将该点加入集合

       for j := 1; j <= n; j++{ //更新dist
           dist[j] = min(dist[j], dist[t] + g[t][j])
       }
   }

习题

LeetCode 743. 网络延迟时间
acwing849

有边数限制的最短路问题-Bellman Ford算法