6C.md

Dijkstra算法

　　Dijkstra算法是寻找单源最短路径的经典算法，其思路与上一节讨论的Prim算法是一致的。只是这次从外围挑选的点，不再是最靠近主集团的点，而是最靠近源点的点。

实现 & 分析

Dijkstra算法的实现与Prim算法大同小异，同样可以用配对堆优化，时间复杂度也是一样的O(VlogV＋E)。

func DijkstraPath(roads [][]graph.Path, start, end int) []int {
    //...
    for !hp.IsEmpty() {
        curr := hp.Top()
        idx := curr.Val.idx
        if idx == end { return trace() }                    //返回最短路径
        curr.Val.idx = fakeIdx                              //移出外围，纳入主集团
        hp.Pop()
        for _, path := range roads[idx] {
            peer := &nodes[path.Next]
            if peer.Val.link == fakeIdx {                   //未涉及点，纳入外围
                peer.Val.link = idx
                peer.Val.dist = curr.Val.dist + path.Weight
                hp.Push(peer)
            } else if peer.Val.idx != fakeIdx {             //外围点
                dist := curr.Val.dist + path.Weight
                if dist < peer.Val.dist {                   //需要调整
                    peer.Val.link = idx                     //更新最近邻
                    peer.Val.dist = dist
                    hp.FloatUp(peer)
    }   }   }   }
    return nil
}

追寻直觉

有些时候，我们仅仅需要一条路径而不强求最短，那么直觉可以帮助我们更快地找到答案。

for _, path := range roads[idx] {
    peer := &nodes[path.Next]
    if peer.Val.link == fakeIdx {
        peer.Val.link = idx
        peer.Val.dist = curr.Val.dist + path.Weight
        //dist记录了起点到当前点的距离，evaluate评估当前点到终点的距离
        peer.Val.weight = peer.Val.dist + evaluate(peer.idx)    //理性+直觉
        hp.Push(peer)                                           //作为选择标准
    } else if peer.Val.idx != fakeIdx {
        dist := curr.Val.dist + path.Weight
        if dist < peer.Val.dist {
            peer.Val.link = idx
            peer.Val.weight -= peer.Val.dist - dist
            peer.Val.dist = dist
            hp.FloatUp(peer)
}   }   }

人算不如天算

从时间复杂度看，Dijkstra算法是已知最快的单源最短路径算法，然而现实中没有这么理想。

我们求有1000个顶点的稀疏图中两两顶点间最短路径的长度：

Prepare Graph [1000 vertexes & 16866 edges]
SPFA:            97.146205ms
Dijkstra:        256.231027ms
Simple Dijkstra: 202.475989ms
Plain Dijkstra:  1.967896522s
Floyd-Warshall:  1.74469448s

---

目录　上一节　下一节