6D.md

SPFA算法

如果边的权可以是负值，那么重复经过可以获益，此时Dijkstra算法中的一选定终身再不能满足要求。

这里，我们先来看看Floyd-Warshall算法。该算法采用浪淘沙式迭代更新，复杂度为O(V³)。

    func FloydWarshall(matrix [][]int) {
        size := len(matrix)
        for k := 0; k < size; k++ {
            for i := 0; i < size; i++ {
                for j := 0; j < size; j++ {
                    if matrix[i][k] != MAX_DIST && matrix[k][j] != MAX_DIST {
                        distance := matrix[i][k] + matrix[k][j]
                        if distance < matrix[i][j] {
                            matrix[i][j] = distance
    }   }   }   }   }   }

精确打击

　　Floyd-Warshall算法的缺点很明显，就是进行了大量不必要的试探性修改。
　　从Dijkstra算法上，我们可以看到一个事实：某个点只有与发生变化的点相邻才可能发生变化。因此，SPFA算法使用一个队列将变化的点记录起来，以实施精确打击。

func SPFA(roads [][]graph.PathS, start int) ([]int, error) {
    size := len(roads)
    if size == 0 || start < 0 || start >= size {
        return nil, errors.New("illegal input")
    }

    q := array.NewQueue[int](size)
    dist := make([]int, size)                   //记录到各点的最短距离
    age := make([]int, size)                    //绝对值记录入队次数
    for i := 0; i < size; i++ {
        dist[i], age[i] = math.MaxInt, 0        //初始皆不可达
    }

    q.Push(start)
    dist[start], age[start] = 0, -1             //负值表示在队列中
    for !q.IsEmpty() {
        curr := q.Pop()
        age[curr] = -age[curr]
        for _, path := range roads[curr] {
            distance := dist[curr] + path.Weight
            peer := path.Next
            if distance < dist[peer] {
                dist[peer] = distance
                if age[peer] >= 0 {             //不在队列中
                    q.Push(peer)
                    age[peer]++
                    if age[peer] > size {       //入队次数超标，必定是有负回路
                        return nil, errors.New("bad loops exist")
                    }
                    age[peer] = -age[peer]      //入队
    }   }   }   }
    return dist, nil
}

性能分析

　　SPFA算法的复杂度取决于点进入队列的次数。点的每一次入队将使与其相连的边被遍历，最坏情况下，边都会被遍历(V-1)次，耗时达O(VE)级。然而，在上一节我们也看到了，实际使用中，该算法用时通常远低于理论上限。

---

目录　上一节　下一节