deepseek VS chatgpt （398）-- 算法导论25.2 6题

福大大架构师每日一题

发布于 2025-02-12 15:36:27

6200

代码可运行

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

运行总次数：0

代码可运行

六、我们怎样才能使用 Floyd-Warshall 算法的输出来检测权重为负值的环路？如果要写代码，请用go语言。

chatgpt：

Floyd-Warshall 算法是用于寻找图中所有顶点之间的最短路径的一种经典算法。在使用 Floyd-Warshall 算法时，我们可以通过检查在算法执行结束后对角线上的结果来检测图中是否存在权重为负值的环路。如果某个顶点到自身的距离变成了负值，那么图中就存在负权重环。

下面是一个使用 Go 语言实现的简单代码，它展示了如何使用 Floyd-Warshall 算法，并检测负权重环的存在：

package main

import (
    "fmt"
    "math"
)

// 定义无限大
const INF = math.MaxInt64

func floydWarshall(graph [][]int) ([][]int, bool) {
    n := len(graph)
    // 创建一个距离矩阵并初始化
    dist := make([][]int, n)
    for i := 0; i < n; i++ {
        dist[i] = make([]int, n)
        for j := 0; j < n; j++ {
            if i == j {
                dist[i][j] = 0
            } else if graph[i][j] == 0 {
                dist[i][j] = INF
            } else {
                dist[i][j] = graph[i][j]
            }
        }
    }

    // Floyd-Warshall 主循环
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF {
                    if dist[i][j] > dist[i][k]+dist[k][j] {
                        dist[i][j] = dist[i][k] + dist[k][j]
                    }
                }
            }
        }
    }

    // 检测负权重环
    for i := 0; i < n; i++ {
        if dist[i][i] < 0 {
            return dist, true // 存在负权重环
        }
    }

    return dist, false // 不存在负权重环
}

func main() {
    // 定义图的邻接矩阵，0 表示没有边
    graph := [][]int{
        {0, 1, 4, 0, 0},
        {0, 0, 2, 5, 0},
        {0, 0, 0, 0, -3},
        {0, 0, 3, 0, 2},
        {0, 0, 0, -1, 0},
    }

    dist, hasNegativeCycle := floydWarshall(graph)

    if hasNegativeCycle {
        fmt.Println("图中存在负权重环。")
    } else {
        fmt.Println("图中不存在负权重环。")
    }

    // 打印最短路径矩阵
    fmt.Println("最短路径矩阵:")
    for _, row := range dist {
        for _, value := range row {
            if value == INF {
                fmt.Printf("INF ")
            } else {
                fmt.Printf("%d ", value)
            }
        }
        fmt.Println()
    }
}

代码解释：

1. 邻接矩阵: 我们使用一个二维切片表示图的邻接矩阵，graph[i][j] 表示从顶点 i 到 j 的边的权重，若没有边则为 0。
2. 初始化距离矩阵: 我们将距离矩阵 dist 初始化为邻接矩阵的值，且对角线（即顶点到自身的距离）设为 0。
3. Floyd-Warshall 算法主循环: 通过三重循环更新每对顶点之间的最短路径。
4. 检测负权重环: 使用结果距离矩阵检查是否有任何顶点 i 的自我距离 dist[i][i] 小于0。
5. 输出结果: 最后输出是否存在负权重环以及最短路径矩阵。

你可以根据这个示例代码来进行测试和修改，以适应自己的需求。

deepseek：

要检测权重为负值的环路，可以使用Floyd-Warshall算法计算后的距离矩阵。若存在某个节点到自身的距离为负数，则说明存在负权环路。以下是Go语言实现：

package main

import (
    "fmt"
    "math"
)

func floydWarshall(graph [][]int) [][]int {
    n := len(graph)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        copy(dist[i], graph[i])
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != math.MaxInt32 && dist[k][j] != math.MaxInt32 && dist[i][j] > dist[i][k]+dist[k][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    return dist
}

func hasNegativeCycle(dist [][]int) bool {
    for i := 0; i < len(dist); i++ {
        if dist[i][i] < 0 {
            return true
        }
    }
    return false
}

func main() {
    // 示例图
    graph := [][]int{
        {0, 1, math.MaxInt32, math.MaxInt32},
        {math.MaxInt32, 0, -1, math.MaxInt32},
        {math.MaxInt32, math.MaxInt32, 0, -1},
        {-1, math.MaxInt32, math.MaxInt32, 0},
    }

    dist := floydWarshall(graph)
    if hasNegativeCycle(dist) {
        fmt.Println("存在负权环路")
    } else {
        fmt.Println("不存在负权环路")
    }
}

步骤解释：

1. Floyd-Warshall算法实现：
- • 初始化距离矩阵dist，拷贝输入的邻接矩阵。
- • 通过三重循环更新所有节点对的最短路径，允许经过中间节点k。
2. 负权环路检测：
- • 遍历每个节点，检查其到自身的距离dist[i][i]。若该值为负，说明存在从i出发并返回i的负权环路。

示例说明： 示例图中存在环路3 → 0 → 1 → 2 → 3，总权重为负。Floyd-Warshall算法计算后，相关节点的自反距离变为负数，从而被检测到负权环路。运行代码将输出“存在负权环路”。

在这里插入图片描述

通义千问：

Floyd-Warshall 算法是一种用于寻找加权图中所有顶点对之间最短路径的算法。它能够处理有向图和负权重边，但不能正确处理包含负权重环路的情况。然而，我们可以利用该算法的输出来检测图中是否存在负权重环路。

检测负权重环路的方法

当使用 Floyd-Warshall 算法计算最短路径时，如果在最终的距离矩阵 dist 中存在一个顶点 v，使得 dist[v][v] < 0，则说明存在一个负权重环路。这是因为正常情况下，任何顶点到自己的最短路径长度应该是 0（如果没有自环的话）。如果某个顶点通过某些边回到自己且总权重为负数，这就表明存在一个负权重环路。

Go语言代码实现

下面是一个简单的Go语言示例，展示了如何使用 Floyd-Warshall 算法并检查负权重环路：

package main

import (
    "fmt"
    "math"
)

const V = 4 // 定义图中的顶点数量

func floydWarshall(graph [][]float64) {
    dist := make([][]float64, V)
    for i := range dist {
        dist[i] = make([]float64, V)
        copy(dist[i], graph[i])
    }

    // 应用Floyd-Warshall算法
    for k := 0; k < V; k++ {
        for i := 0; i < V; i++ {
            for j := 0; j < V; j++ {
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    // 检查负权重环路
    for i := 0; i < V; i++ {
        if dist[i][i] < 0 {
            fmt.Printf("图中存在负权重环路，位于顶点 %d\n", i)
            return
        }
    }

    // 输出最短距离矩阵
    fmt.Println("最短路径矩阵:")
    for i := 0; i < V; i++ {
        for j := 0; j < V; j++ {
            if dist[i][j] == math.MaxFloat64 {
                fmt.Print("INF ")
            } else {
                fmt.Printf("%3.1f ", dist[i][j])
            }
        }
        fmt.Println()
    }
}

func main() {
    graph := [][]float64{
        {0, 3, math.MaxFloat64, 7},
        {8, 0, 2, math.MaxFloat64},
        {5, math.MaxFloat64, 0, 1},
        {2, math.MaxFloat64, math.MaxFloat64, 0},
    }

    floydWarshall(graph)
}

请注意，在这个例子中，我们初始化了一个图，并使用了 Floyd-Warshall 算法来计算所有顶点之间的最短路径。然后，我们遍历每个顶点，以检查是否存在负权重环路。如果有，程序将打印一条消息指出其位置；否则，它将打印出最短路径矩阵。你可以根据需要调整图的大小(V)和边的权重。

豆包：

Floyd-Warshall 算法概述

Floyd-Warshall 算法是一种用于求解图中所有顶点对之间最短路径的动态规划算法。其基本思想是通过逐步考虑所有可能的中间顶点，来更新每对顶点之间的最短路径。

检测负权重环路的原理

在 Floyd-Warshall 算法执行完毕后，如果图中存在负权重环路，那么必然存在某个顶点 i，使得从 i 到 i 的最短路径长度为负数（即 dist[i][i] < 0）。这是因为沿着负权重环路绕一圈，路径长度会不断减小，最终使得回到自身的路径长度为负。

Go 语言实现

package main

import (
    "fmt"
    "math"
)

const INF = math.MaxInt32

// FloydWarshall 实现 Floyd-Warshall 算法
func FloydWarshall(graph [][]int) ([][]int, bool) {
    n := len(graph)
    // 初始化距离矩阵
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = graph[i][j]
        }
    }

    // 动态规划更新距离矩阵
    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF && dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    // 检测负权重环路
    for i := 0; i < n; i++ {
        if dist[i][i] < 0 {
            return dist, true
        }
    }

    return dist, false
}

func main() {
    // 示例图的邻接矩阵表示
    graph := [][]int{
        {0, 1, INF, INF},
        {INF, 0, -1, INF},
        {INF, INF, 0, -1},
        {-1, INF, INF, 0},
    }

    dist, hasNegativeCycle := FloydWarshall(graph)

    if hasNegativeCycle {
        fmt.Println("图中存在负权重环路")
    } else {
        fmt.Println("图中不存在负权重环路")
    }

    // 输出所有顶点对之间的最短路径长度
    fmt.Println("所有顶点对之间的最短路径长度:")
    for i := range dist {
        for j := range dist[i] {
            if dist[i][j] == INF {
                fmt.Print("INF ")
            } else {
                fmt.Print(dist[i][j], " ")
            }
        }
        fmt.Println()
    }
}

代码解释

1. 初始化距离矩阵：将输入的图的邻接矩阵复制到 dist 矩阵中。
2. 动态规划更新：通过三重循环，逐步考虑所有可能的中间顶点 k，更新每对顶点 (i, j) 之间的最短路径长度。
3. 检测负权重环路：遍历 dist 矩阵的对角线元素，如果存在 dist[i][i] < 0，则说明图中存在负权重环路。
4. 输出结果：根据检测结果输出是否存在负权重环路，并输出所有顶点对之间的最短路径长度。

复杂度分析

• 时间复杂度：，其中是图中顶点的数量。
• 空间复杂度：，主要用于存储距离矩阵。

文心一言：

Floyd-Warshall 算法是一种用于计算所有节点对之间最短路径的动态规划算法。其输出可以用来检测图中是否存在权重为负值的环路。如果存在从某个节点出发，通过一系列边回到该节点且总权重为负的路径，那么就说明图中存在权重为负值的环路。

在 Floyd-Warshall 算法的实现中，如果最终得到的 dist 矩阵中，存在 dist[i][i] 为负值的情况（i 为某个节点），则表明图中存在权重为负值的环路。

下面是用 Go 语言实现 Floyd-Warshall 算法并检测权重为负值的环路的代码：

package main
 
import (
    "fmt"
    "math"
)
 
const INF = math.MaxInt32
 
// Floyd-Warshall algorithm to find shortest paths between all pairs of vertices
func floydWarshall(graph [][]int) [][]int {
    V := len(graph)
    dist := make([][]int, V)
    for i := range dist {
        dist[i] = make([]int, V)
        copy(dist[i], graph[i])
    }
 
    for k := 0; k < V; k++ {
        for i := 0; i < V; i++ {
            for j := 0; j < V; j++ {
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }
 
    return dist
}
 
// Function to check for negative weight cycles using Floyd-Warshall output
func hasNegativeWeightCycle(dist [][]int) bool {
    for i := range dist {
        if dist[i][i] < 0 {
            return true
        }
    }
    return false
}
 
func main() {
    // Example graph represented as an adjacency matrix
    // INF indicates no direct edge between two vertices
    graph := [][]int{
        {0, 3, INF, -1},
        {2, 0, INF, INF},
        {INF, -4, 0, 1},
        {INF, INF, INF, 0},
    }
 
    dist := floydWarshall(graph)
 
    fmt.Println("Shortest distances between every pair of vertices:")
    for _, row := range dist {
        fmt.Println(row)
    }
 
    if hasNegativeWeightCycle(dist) {
        fmt.Println("Graph contains a negative weight cycle.")
    } else {
        fmt.Println("Graph does not contain a negative weight cycle.")
    }
}

代码说明： INF 常量：表示无穷大，用于初始化图中没有直接边的位置。 floydWarshall 函数：实现了 Floyd-Warshall 算法，计算所有节点对之间的最短路径。 hasNegativeWeightCycle 函数：检查 dist 矩阵的对角线元素，如果某个 dist[i][i] 为负值，则说明存在权重为负值的环路。 main 函数：定义一个示例图（使用邻接矩阵表示），调用 Floyd-Warshall 算法并检查是否存在权重为负值的环路。示例图： graph := [][]int{ {0, 3, INF, -1}, {2, 0, INF, INF}, {INF, -4, 0, 1}, {INF, INF, INF, 0}, } 在这个示例图中，节点 0 到节点 3 有一条权重为 -1 的边，节点 2 到节点 0 有一条权重为 -4 的边。通过这两条边可以形成一个权重为负值的环路（0 -> 3 -> 2 -> 0）。

运行代码后，将输出最短路径矩阵，并显示图中是否存在权重为负值的环路。

讯飞星火：

Floyd-Warshall 算法是一种用于计算图中所有顶点对之间最短路径的动态规划算法。它不仅可以找到最短路径，还可以检测是否存在负权重环路。

在 Floyd-Warshall 算法中，如果存在一个从某个顶点出发并返回到该顶点的路径，其路径上的总权重小于零，则说明存在一个负权重环路。

以下是使用 Go 语言实现 Floyd-Warshall 算法并检测负权重环路的代码示例：

package main

import (
    "fmt"
    "math"
)

const INF = math.MaxFloat64

func floydWarshall(graph [][]float64) ([][]float64, bool) {
    n := len(graph)
    dist := make([][]float64, n)
    for i := range dist {
        dist[i] = make([]float64, n)
        for j := range dist[i] {
            if i == j {
                dist[i][j] = 0
            } else if graph[i][j] != INF {
                dist[i][j] = graph[i][j]
            } else {
                dist[i][j] = INF
            }
        }
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF && dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    // Check for negative weight cycle
    for i := 0; i < n; i++ {
        if dist[i][i] < 0 {
            return dist, true // Negative weight cycle detected
        }
    }

    return dist, false // No negative weight cycle detected
}

func main() {
    graph := [][]float64{
        {0, 1, INF, INF},
        {INF, 0, -1, INF},
        {INF, INF, 0, -1},
        {-1, INF, INF, 0},
    }

    dist, hasNegativeCycle := floydWarshall(graph)

    if hasNegativeCycle {
        fmt.Println("Graph contains a negative weight cycle")
    } else {
        fmt.Println("Shortest distance matrix:")
        for _, row := range dist {
            fmt.Println(row)
        }
    }
}

解释：

1. 初始化：我们首先初始化 dist 矩阵，其中 dist[i][j] 表示从顶点 i 到顶点 j 的最短距离。如果两个顶点之间没有直接边，则距离为无穷大（INF）。
2. 更新距离：通过三重循环更新 dist 矩阵，以考虑所有可能的中间顶点 k。如果通过 k 可以缩短从 i 到 j 的距离，则更新 dist[i][j]。
3. 检测负权重环路：最后，检查 dist[i][i] 是否小于零。如果是，则说明存在负权重环路。

运行上述代码，如果图中存在负权重环路，程序将输出相应的提示信息；否则，它将打印出所有顶点对之间的最短距离矩阵。

360智脑：

原理分析 Floyd-Warshall算法是一种用于求解图中所有节点对之间最短路径的动态规划算法。其基本思想是通过不断尝试所有可能的中间节点，更新节点对之间的最短距离。时间复杂度为 O ( V 3 ) O(V 3 )，其中 V V 是图中节点的数量。

若图中存在权重为负值的环路，那么在经过一系列的节点更新后，将会出现某个节点到自身的最短路径距离为负值的情况。这是因为在负权环中不断绕圈会使得路径权重不断减小。因此，我们可以在Floyd-Warshall算法执行完成后，检查所有节点到自身的最短路径距离。如果存在节点 i i 使得 d i s t [ i ] [ i ] < 0 dist[i][i]<0，则说明图中存在负权环路。

Go语言代码实现 package main

import ( "fmt" "math" )

const INF = math.MaxInt32

// FloydWarshall 实现Floyd-Warshall算法并检测负权环路 func FloydWarshall(graph [][]int) bool { V := len(graph) // 初始化距离矩阵 dist := make([][]int, V) for i := range dist { dist[i] = make([]int, V) for j := range dist[i] { if i == j { dist[i][j] = 0 } else if graph[i][j] == 0 { dist[i][j] = INF } else { dist[i][j] = graph[i][j] } } }

// Floyd-Warshall算法核心 
for k := 0; k < V; k++ { 
    for i := 0; i < V; i++ { 
        for j := 0; j < V; j++ { 
            if dist[i][k]!= INF && dist[k][j]!= INF && dist[i][k]+dist[k][j] < dist[i][j] { 
                dist[i][j] = dist[i][k] + dist[k][j] 
            } 
        } 
    } 
} 

// 检测负权环路 
for i := 0; i < V; i++ { 
    if dist[i][i] < 0 { 
        return true 
    } 
} 
return false

}

func main() { // 示例图的邻接矩阵表示 graph := [][]int{ {0, 1, 0}, {0, 0, -1}, {0, 0, 0}, }

if FloydWarshall(graph) { 
    fmt.Println("图中存在负权环路") 
} else { 
    fmt.Println("图中不存在负权环路") 
}

} 代码解释初始化距离矩阵：我们使用 dist 矩阵来存储节点对之间的最短距离。当 i == j 时，dist[i][j] 初始化为 0；当 graph[i][j] 为 0 时，表示节点 i 到节点 j 没有直接连接，dist[i][j] 初始化为无穷大 INF；否则，dist[i][j] 初始化为 graph[i][j]。 Floyd-Warshall算法核心：通过三重循环，不断尝试所有可能的中间节点 k，更新节点对 (i, j) 之间的最短距离。检测负权环路：在算法执行完成后，检查所有节点到自身的最短路径距离。如果存在 dist[i][i] < 0，则说明图中存在负权环路，返回 true；否则返回 false。复杂度分析时间复杂度： O ( V 3 ) O(V 3 )，其中 V V 是图中节点的数量。空间复杂度： O ( V 2 ) O(V 2 )，主要用于存储距离矩阵。

智谱清言：

Floyd-Warshall 算法用于计算图中所有顶点对之间的最短路径。如果图中存在权重为负值的环路，那么在最短路径的计算过程中，某些顶点对之间的最短路径会陷入一个无限循环，因为每次通过这个环路，路径的总权重都会减少。因此，要检测权重为负值的环路，我们可以在Floyd-Warshall算法完成后检查对角线元素是否出现了负值。如果存在顶点v使得dist[v][v] < 0，则图中存在权重为负值的环路。以下是使用Go语言实现的Floyd-Warshall算法，并在最后检查是否存在权重为负值的环路：

package main
import (
    "fmt"
)
// Number of vertices in the graph
const V = 4
// Define Infinite as a large enough value. This value will be used
// for vertices not connected to each other
var INF = 99999
// A utility function to print the solution
func printSolution(dist [][]int) {
    for i := 0; i < V; i++ {
        for j := 0; j < V; j++ {
            if dist[i][j] == INF {
                fmt.Printf("%7s", "INF")
            } else {
                fmt.Printf("%7d", dist[i][j])
            }
        }
        fmt.Println()
    }
}
// Solves the all-pairs shortest path problem using Floyd-Warshall algorithm
func floydWarshall(graph [][]int) {
    // dist[][] will be the output matrix that will finally have the shortest distances between every pair of vertices
    dist := make([][]int, V)
    for i := range dist {
        dist[i] = make([]int, V)
        copy(dist[i], graph[i])
    }
    // Add all vertices one by one to the set of intermediate vertices.
    // ---> Before start of an iteration, we have shortest distances between all pairs of vertices such that the shortest distances consider only the vertices in set {0, 1, 2, .. k-1} as intermediate vertices.
    // ---> After the end of an iteration, vertex no. k is added to the set of intermediate vertices and the set becomes {0, 1, 2, .. k}
    for k := 0; k < V; k++ {
        for i := 0; i < V; i++ {
            for j := 0; j < V; j++ {
                dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
            }
        }
    }
    // Check for negative-weight cycles.
    for i := 0; i < V; i++ {
        if dist[i][i] < 0 {
            fmt.Println("Graph contains negative weight cycle")
            return
        }
    }
    // Print the shortest distance matrix
    printSolution(dist)
}
// A utility function to find the minimum of two integers
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func main() {
    // Let us create the following weighted graph
    // (The given graph has negative weight cycle)
    graph := [][]int{
        {0, 5, INF, 10},
        {INF, 0, 3, INF},
        {INF, INF, 0, 1},
        {INF, INF, INF, 0},
    }
    // Run the Floyd-Warshall algorithm
    floydWarshall(graph)
}

在上面的代码中，我们首先定义了一个图，并使用Floyd-Warshall算法计算所有顶点对之间的最短路径。在算法的最后，我们检查对角线元素dist[i][i]，如果它小于0，则表示图中存在权重为负值的环路。如果存在这样的环路，我们打印一条消息并返回，否则打印出最短路径矩阵。

天工：

1. 检测原理
- • Floyd - Warshall算法用于在图中找到所有顶点对之间的最短路径。在执行Floyd - Warshall算法的过程中，如果存在一个顶点(i)，使得(dist[i][i]<0)（(dist)是存储最短路径距离的二维数组），那么图中存在一个包含顶点(i)的权重为负值的环路。
2. Go语言示例代码
- • 以下是一个使用Go语言实现的基于Floyd - Warshall算法输出检测负权环路的示例代码：

package main

import (
    "fmt"
)

// FloydWarshall函数执行Floyd - Warshall算法并检测负权环路
func FloydWarshall(graph [][]int) bool {
    numVertices := len(graph)
    dist := make([][]int, numVertices)
    for i := range dist {
        dist[i] = make([]int, numVertices)
        for j := range dist[i] {
            dist[i][j] = graph[i][j]
        }
    }

    for k := 0; k < numVertices; k++ {
        for i := 0; i < numVertices; i++ {
            for j := 0; j < numVertices; j++ {
                if dist[i][k]+dist[k][j]<dist[i][j] {
                    dist[i][j]=dist[i][k] + dist[k][j]
                }
            }
        }
    }

    // 检测负权环路
    for i := 0; i < numVertices; i++ {
        if dist[i][i]<0 {
            return true
        }
    }
    return false
}

你可以使用以下方式调用这个函数：

func main() {
    // 示例图的邻接矩阵表示
    graph := [][]int{
        {0, 5, -1},
        {0, 0, 2},
        {1, 0, 0},
    }
    hasNegativeCycle := FloydWarshall(graph)
    if hasNegativeCycle {
        fmt.Println("图中存在负权环路")
    } else {
        fmt.Println("图中不存在负权环路")
    }
}

在这个代码中，首先实现了Floyd - Warshall算法来计算所有顶点对之间的最短路径距离。然后，通过检查对角线元素(dist[i][i])是否小于(0)来确定是否存在负权环路。

kimi：

Floyd-Warshall 算法检测负权重环路的方法 Floyd-Warshall 算法可以通过检查其输出矩阵的对角线元素来检测负权重环路。如果矩阵的某个对角线元素 dii 小于 0，即 dii<0，则表示图中存在负权重环路。 Go 语言实现代码以下是使用 Go 语言实现 Floyd-Warshall 算法并检测负权重环路的代码：

package main

import (
    "fmt"
    "math"
)

const INF = math.MaxInt32

// FloydWarshall 实现 Floyd-Warshall 算法
func FloydWarshall(graph [][]int) [][]int {
    n := len(graph)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = graph[i][j]
        }
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k] != INF && dist[k][j] != INF && dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    return dist
}

// DetectNegativeCycle 检测负权重环路
func DetectNegativeCycle(dist [][]int) bool {
    n := len(dist)
    for i := 0; i < n; i++ {
        if dist[i][i] < 0 {
            return true
        }
    }
    return false
}

func main() {
    // 示例图的邻接矩阵
    graph := [][]int{
        {0, 6, INF, 1},
        {INF, 0, 5, 2},
        {INF, INF, 0, INF},
        {INF, INF, -1, 0},
    }

    // 计算所有顶点对的最短路径
    dist := FloydWarshall(graph)

    // 检测是否存在负权重环路
    if DetectNegativeCycle(dist) {
        fmt.Println("图中存在负权重环路")
    } else {
        fmt.Println("图中不存在负权重环路")
    }

    // 打印最短路径矩阵
    fmt.Println("最短路径矩阵：")
    for _, row := range dist {
        fmt.Println(row)
    }
}

代码说明 FloydWarshall 函数：实现 Floyd-Warshall 算法，计算图中所有顶点对的最短路径。 DetectNegativeCycle 函数：检查 Floyd-Warshall 算法的输出矩阵的对角线元素，判断是否存在负权重环路。主函数：定义一个示例图的邻接矩阵，调用 FloydWarshall 函数计算最短路径矩阵，并通过 DetectNegativeCycle 函数检测负权重环路。运行此代码可以检测图中是否存在负权重环路，并打印最短路径矩阵。

腾讯元宝：

Floyd-Warshall算法是一种用于查找给定加权图中所有顶点对之间的最短路径的算法。该算法也可以用来检测图中是否存在权重为负的环路。如果一个图中存在权重为负的环路，那么从该环路上的任一顶点出发，沿着环路走一圈后，可以得到一个更短的路径，这意味着最短路径的定义被违反了。

在Floyd-Warshall算法中，我们维护一个二维数组dist，其中dist[i][j]表示从顶点i到顶点j的最短路径的权重。如果在算法执行完毕后，存在某个dist[i][i]（即从顶点i到它自己的距离）是负数，那么就意味着图中存在一个权重为负的环路。

以下是使用Go语言实现Floyd-Warshall算法并检测负权重环路的示例代码：

package main

import (
    "fmt"
    "math"
)

const INF = math.MaxInt32

// FloydWarshall computes the shortest paths between all pairs of vertices in a graph.
// It returns the distance matrix and a boolean indicating whether a negative cycle exists.
func FloydWarshall(graph [][]int) ([][]int, bool) {
    n := len(graph)
    dist := make([][]int, n)
    for i := range dist {
        dist[i] = make([]int, n)
        copy(dist[i], graph[i])
    }

    for k := 0; k < n; k++ {
        for i := 0; i < n; i++ {
            for j := 0; j < n; j++ {
                if dist[i][k]+dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j]
                }
            }
        }
    }

    // Check for negative cycles
    hasNegativeCycle := false
    for i := 0; i < n; i++ {
        if dist[i][i] < 0 {
            hasNegativeCycle = true
            break
        }
    }

    return dist, hasNegativeCycle
}

func main() {
    // Example graph with a negative cycle
    graph := [][]int{
        {0, 3, INF, 7},
        {8, 0, 2, INF},
        {5, INF, 0, 1},
        {2, INF, INF, 0},
    }

    // Introduce a negative cycle
    graph[3][1] = -10

    dist, hasNegativeCycle := FloydWarshall(graph)

    if hasNegativeCycle {
        fmt.Println("The graph contains a negative weight cycle.")
    } else {
        fmt.Println("Shortest distances between all pairs of vertices:")
        for _, row := range dist {
            fmt.Println(row)
        }
    }
}

在这段代码中，我们首先定义了一个INF常量来表示无穷大，即两个顶点之间没有直接路径。然后我们定义了FloydWarshall函数，它接受一个图的邻接矩阵表示，并返回所有顶点对之间的最短距离矩阵以及一个布尔值，指示图中是否存在负权重环路。

在main函数中，我们创建了一个示例图，并人为地引入了一个负权重环路。然后我们调用FloydWarshall函数，并根据返回的布尔值判断是否存在负权重环路。

如果存在负权重环路，程序将输出相应的信息；如果不存在，它将输出所有顶点对之间的最短距离。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2025-02-10，如有侵权请联系 cloudcommunity@tencent.com 删除

算法