3.1 最短路径算法-Dijkstra-编程书籍在线阅读平台-duidaima 堆代码

3.1 最短路径算法-Dijkstra

算法描述

这个算法是通过为每个顶点 v 保留目前为止所找到的从 s 到 v 的最短路径来工作的。初始时，原点 s 的路径权重被赋为 0 （d[s] = 0）。若对于顶点 s 存在能直接到达的边（s,m），则把 d[m]设为 w（s, m）,同时把所有其他（s 不能直接到达的）顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径（对于所有顶点的集合 V 中的任意顶点 v，若 v 不为 s 和上述 m 之一， d[v] = ∞）。当算法结束时，d[v] 中存储的便是从 s 到 v 的最短路径，或者如果路径不存在的话是无穷大。

边的拓展是 Dijkstra 算法的基础操作：如果存在一条从 u 到 v 的边，那么从 s 到 v 的最短路径可以通过将边（u, v）添加到尾部来拓展一条从 s 到 v 的路径。这条路径的长度是 d[u] + w(u, v)。如果这个值比目前已知的 d[v] 的值要小，我们可以用新值来替代当前 d[v] 中的值。拓展边的操作一直运行到所有的 d[v] 都代表从 s 到 v 的最短路径的长度值。此算法的组织令 d[u] 达到其最终值时，每条边（u, v）都只被拓展一次。

算法维护两个顶点集合 S 和 Q。集合 S 保留所有已知最小 d[v] 值的顶点 v ，而集合 Q 则保留其他所有顶点。集合 S 初始状态为空，而后每一步都有一个顶点从 Q 移动到 S。这个被选择的顶点是 Q 中拥有最小的 d[u] 值的顶点。当一个顶点 u 从 Q 中转移到了 S 中，算法对 u 的每条外接边 (u, v) 进行拓展。

代码实现-Golang
github

package ShortestPath

import (
    "errors"

    "container/list"

    "github.com/mohuishou/algorithm/Graph"
)

//INF 无穷大
const INF = 0xffffff

//Dijkstra 算法
//一种求单源最短路径的算法
func Dijkstra(graph Graph.Graph, s Graph.VextexType, dist[] Graph.EdgeType, path[] Graph.VextexType) {
    visited: = make([] bool, graph.VNum)
        //初始化
    for i: = 0;i < graph.VNum;i++{
        dist[i] = INF //距离为无穷大
        path[i] = -1 //没有上一个节点
        visited[i] = false
    }
    path[s] = s
    dist[s] = 0

    //使用list实现一个队列操作
    q: = list.New()

    //将点s入队
        q.PushBack(s)
    for q.Len() != 0 {
        u: = q.Front().Value.(Graph.VextexType)
        q.Remove(q.Front())
        //如果该点周围的点已经走过，则无需再走
        if visited[u] {
            continue
        }

        //将该点加入已观察
        visited[u] = true

        e: = graph.G[u].FisrtEdge

            for e != nil {
            //这条边下的顶点
            v: = e.V

            //如果该点尚未走过，并且当前点的距离加上边的距离小于之前该点的距离，那么就更新该点的距离
                if visited[v] == false && dist[v] > dist[u] + e.Weight {
                dist[v] = dist[u] + e.Weight //更新该点距离
                path[v] = u //更新父节点
                q.PushBack(v) //将该点入队
            }
            e = e.Next
        }

    }

}

//GetPath 通过路径获得到指定目的节点的路径
func GetPath(path[] Graph.VextexType, t Graph.VextexType)([] Graph.VextexType, error) {
    tPath: = make([] Graph.VextexType, 0)
    for {
        tPath = append(tPath, t)
        if path[t] == -1 {
            return nil, errors.New("不存在到该节点的路径")
        }
        if t == path[t] {
            return tPath, nil
        }
        t = path[t]
    }
}

留下你的读书笔记
你还没登录，点击这里
 用户笔记留言