743. 网络延迟

Bellman-Ford算法

最多遍历N-1轮所有边，得到最短或者最长路径。

时间复杂度：O(N^2)
空间复杂度：O(N)

func networkDelayTime(times [][]int, n int, k int) int {
    dist := make([]int, n+1)
    const inf = math.MaxInt / 2

    for i, _ := range dist {
        if i == k {
            dist[i] = 0
        } else {
            dist[i] = inf
        }
    }

    fmt.Println(dist)
    for j := 1; j < n; j++ {
        flag := false
        for i := 0; i < len(times); i++ {
            x := times[i][0]
            y := times[i][1]
            z := times[i][2]

            if dist[y] > dist[x] + z {
                // fmt.Printf("x: %v, y: %v, z: %v\n", x, y, z)
                dist[y] = dist[x] + z
                // fmt.Printf("dist[x]: %v, dist[y]: %v\n",dist[x], dist[y])
                flag = true
            }
        }
        if !flag {
            break
        }
    }

    ans := 0

    for i := 1; i < len(dist); i++ {
        if dist[i] == inf {
            return -1
        }

        if ans < dist[i] {
            ans = dist[i]
        }
    }

    return ans
}