Dijkstra算法理论与实现

Dijkstra算法理论

在带权图中，从一个单源节点到其他节点寻找最短路径，是典型的单源最短路径问题。Dijkstra算法由荷兰计算机科学家狄克斯特拉于1959年提出，适用于有向图的最短路径计算。

基本思想

初始化：指定起点s，初始化两个集合S和U。S记录已求出最短路径的顶点，U记录尚未求出的顶点及其到起点s的距离。

迭代过程：

从U中选择距离s最短的顶点k，加入S。

更新U中所有顶点到s的距离，基于k的最短路径。

重复上述步骤直至所有顶点都被计算。

操作步骤

初始时，S包含起点s，U包含其他所有顶点，初始距离为∞。

每次从U中选出距离s最短的顶点k，加入S。

更新所有顶点到s的最短距离，基于k的路径。

重复步骤2-4，直到S包含所有顶点。

Dijkstra算法Golang实现

func Dijkstra(D [LEN][LEN]int, v int) {    if v < 0 || v >= LEN {        fmt.Println("错误节点输入！")        return    }        // 初始化距离矩阵    for i := 0; i < LEN; i++ {        for j := 0; j < LEN; j++ {            if D[i][j] == -1 {                D[i][j] = 9999999            }        }    }        // 初始化S和U    var S []int    S = append(S, v)        for i := 0; i < LEN; i++ {        if !contains(S, i) && D[i][v] == 9999999 {            min = D[i][v]            index = i            break        }    }        if min == 9999999 {        fmt.Printf("最小值min=%d\n", min)        return    }        S = append(S, index)        for i := 0; i < LEN; i++ {        for j := 0; j < LEN; j++ {            if i == j || v == j {                continue            }            if D[i][j] > D[i][index] + D[index][j] {                D[i][j] = D[i][index] + D[index][j]                Path[i][j] = index            }        }    }        // 重复上述过程直到S包含所有顶点}

Floyd算法理论

Floyd算法（插点法）用于多源最短路径计算，通过三重循环更新所有点对的最短路径。其核心思想是通过松弛操作，逐步优化路径距离。

核心思想

初始化：使用邻接矩阵D，初始时D[i][j]为原始权值。

三重循环：

选择每个点i作为中间过渡点。

遍历所有点对(i,j)，判断是否通过i的路径更短。

如果更短，更新D[i][j]和路径信息。

优缺点

优点：代码简单，计算任意两点间最短路径。缺点：时间复杂度较高，不适合大规模数据。

Floyd算法Golang实现

func Floyd(D [LEN][LEN]int) {    // 初始化路径矩阵    var Path [LEN][LEN]int    for i := 0; i < LEN; i++ {        for j := 0; j < LEN; j++ {            Path[i][j] = -1        }    }        for i := 0; i < LEN; i++ {        for j := 0; j < LEN; j++ {            if D[i][j] == -1 {                D[i][j] = 9999999            }        }    }        for v := 0; v < LEN; v++ {        for i := 0; i < LEN; i++ {            for j := 0; j < LEN; j++ {                if i == j || v == i || v == j {                    continue                }                if D[i][j] > D[i][v] + D[v][j] {                    D[i][j] = D[i][v] + D[v][j]                    Path[i][j] = v                }            }        }    }        // 输出结果    for i := 0; i < LEN; i++ {        for j := 0; j < LEN; j++ {            if D[i][j] == 9999999 {                D[i][j] = -1            }        }    }        for i := 0; i < LEN; i++ {        for j := 0; j < LEN; j++ {            fmt.Printf("点%d到点%d的最短距离为%d\n", i, j, D[i][j])        }    }}

总结

两种算法均基于贪心思想，Dijkstra单源最短路径，Floyd多源最短路径。Dijkstra每次计算单个源点最短路径，Floyd一次性计算所有点对。两者时间复杂度均为O(N^3)，适用于小规模数据。

转载地址：http://swob.baihongyu.com/

你可能感兴趣的文章