本文共 2655 字，大约阅读时间需要 8 分钟。

Dijkstra算法理论与实现

Dijkstra算法理论

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

基本思想

操作步骤

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

核心思想

优缺点

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

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/