文心一言 VS 讯飞星火 VS chatgpt （378）-- 算法导论24.4 10题

package main

import(
"fmt"
"math"
)

const(
    INF = math.MaxInt32
)

// Edge represents an edge in the graph
typeEdgestruct{
from, to, weight int
}

// BellmanFord solves the difference constraint system using Bellman-Ford algorithm
func BellmanFord(edges []Edge, numVertices int, source int)([]int,bool){
// Initialize distances from source to all other vertices as infinite
    distances :=make([]int, numVertices)
for i :=range distances {
        distances[i]= INF
}
    distances[source]=0

// Relax all edges |V| - 1 times. A simple shortest path from source to any other
// vertex can have at-most |V| - 1 edges
for i :=0; i < numVertices-1; i++{
for _, edge :=range edges {
            u, v, w := edge.from, edge.to, edge.weight
if distances[u]!= INF && distances[u]+w < distances[v]{
                distances[v]= distances[u]+ w
}
}
}

// Check for negative-weight cycles. The above step guarantees shortest distances
// if the graph doesn't contain negative weight cycle. If we get a shorter path,
// then there is a cycle.
for _, edge :=range edges {
        u, v, w := edge.from, edge.to, edge.weight
if distances[u]!= INF && distances[u]+w < distances[v]{
// Graph contains negative weight cycle
returnnil,false
}
}

return distances,true
}

func main(){
// Example input: Convert linear constraints to difference constraints
// Constraints:
// x1 <= 3
// -x2 <= 2
// x3 - x1 <= 1
// x2 - x3 <= -1
// x1 - x2 <= 0

    edges :=[]Edge{
{0,1,3},// x1 - x0 <= 3  ->  x1 <= 3
{0,2,2},// x0 - x2 <= 2  ->  -x2 <= 2
{1,3,1},// x3 - x1 <= 1
{2,3,-1},// x2 - x3 <= -1 -> equivalent to x3 - x2 <= 1 (reversed for graph representation)
{1,2,0},// x1 - x2 <= 0
}

    numVertices :=4// x0, x1, x2, x3
    source :=0// x0 is the source (auxiliary variable)

    distances, ok :=BellmanFord(edges, numVertices, source)
if!ok {
        fmt.Println("Graph contains a negative weight cycle, no solution exists.")
}else{
        fmt.Println("Shortest distances from source (x0):")
for i, dist :=range distances {
            fmt.Printf("x%d: %d\n", i, dist)
}
}
}

package main

import(
"fmt"
"math"
)

// BellmanFordModified solves the linear programming problem using a modified Bellman-Ford algorithm.
func BellmanFordModified(A [][]float64, b []float64)([]float64,bool){
    n :=len(b)
    dist :=make([]float64, n)
for i :=range dist {
        dist[i]= math.Inf(1)// Initialize distances to infinity
}
    dist[0]=0// Assuming the source is at index 0

// Relax edges up to |V| - 1 times
for i :=0; i < n-1; i++{
        updated :=false
for j :=0; j <len(A); j++{
            u :=int(A[j][0])
            v :=int(A[j][1])
            weight := A[j][2]
if dist[u]!= math.Inf(1)&& dist[u]+weight < dist[v]{
                dist[v]= dist[u]+ weight
                updated =true
}
}
if!updated {
break// No more updates, early exit
}
}

// Check for negative cycles
for j :=0; j <len(A); j++{
        u :=int(A[j][0])
        v :=int(A[j][1])
        weight := A[j][2]
if dist[u]!= math.Inf(1)&& dist[u]+weight < dist[v]{
returnnil,false// Negative cycle detected
}
}

return dist,true
}

func main(){
// Example usage:
// A matrix where each row represents [u, v, weight]
    A :=[][]float64{
{0,1,5},
{1,2,2},
{2,3,3},
{3,1,-6},
}
    b :=[]float64{0,0,0,0}// This example does not use b directly, but it's part of the input format.

    dist, solvable :=BellmanFordModified(A, b)
if solvable {
        fmt.Println("Shortest path distances:", dist)
}else{
        fmt.Println("The system has a negative cycle and no solution exists.")
}
}

package main

import(
"fmt"
"math"
)

typeEdgestruct{
fromint
    to   int
    weight float64
}

func bellmanFord(n int, edges []Edge, source int)([]float64,bool){
    dist :=make([]float64, n)
for i :=range dist {
        dist[i]= math.Inf(1)
}
    dist[source]=0

// Relax edges repeatedly
for i :=0; i < n-1; i++{
for _, edge :=range edges {
if dist[edge.from]+edge.weight < dist[edge.to]{
                dist[edge.to]= dist[edge.from]+ edge.weight
}
}
}

// Check for negative-weight cycles
for _, edge :=range edges {
if dist[edge.from]+edge.weight < dist[edge.to]{
returnnil,false// Negative weight cycle detected
}
}

return dist,true
}

func main(){
// Example constraints
    constraints :=[]struct{
        variable int
        bound    float64
        isPositive bool// true for x_i <= b_k, false for -x_i <= b_k
}{
{0,5,true},
{1,3,true},
{0,-2,false},
{1,-1,false},
}

    n :=2// Number of variables
    source := n // Source node (n+1)

    edges :=make([]Edge,0)

// Add edges for constraints
for _, c :=range constraints {
if c.isPositive {
            edges =append(edges,Edge{source, c.variable, c.bound})
}else{
            edges =append(edges,Edge{c.variable, source,-c.bound})
}
}

// Add zero-weight edges from source to all variables
for i :=0; i < n; i++{
        edges =append(edges,Edge{source, i,0})
}

    dist, hasSolution := bellmanFord(n+1, edges, source)

if!hasSolution {
        fmt.Println("No solution exists due to a negative weight cycle.")
}else{
        fmt.Println("Solution found:")
for i :=0; i < n; i++{
            fmt.Printf("x%d = %f\n", i, dist[i])
}
}
}

package main

import(
"fmt"
"math"
)

// 边的结构体
typeEdgestruct{
from, to, weight int
}

// Bellman-Ford 算法
func BellmanFord(vertices int, edges []Edge, source int)([]float64,bool){
    dist :=make([]float64, vertices)
for i :=range dist {
        dist[i]= math.Inf(1)
}
    dist[source]=0

// 松弛边 |V| - 1 次
for i :=0; i < vertices-1; i++{
for _, edge :=range edges {
if dist[edge.from]!= math.Inf(1)&& dist[edge.from]+float64(edge.weight)< dist[edge.to]{
                dist[edge.to]= dist[edge.from]+float64(edge.weight)
}
}
}

// 检测负权环
for _, edge :=range edges {
if dist[edge.from]!= math.Inf(1)&& dist[edge.from]+float64(edge.weight)< dist[edge.to]{
returnnil,true// 存在负权环
}
}

return dist,false
}

func main(){
    vertices :=5// 变量数量，例如 x1, x2, x3, x4 每个对应一个节点
    edges :=[]Edge{
{4,0,10},// x1 <= 10
{4,1,15},// x2 <= 15
{4,2,5},// x3 <= 5
{0,4,-10},// -x1 <= -10
{1,4,-15},// -x2 <= -15
{2,4,-5},// -x3 <= -5
}

    dist, hasNegativeCycle :=BellmanFord(vertices, edges,4)

if hasNegativeCycle {
        fmt.Println("存在负权环")
}else{
        fmt.Println("最优解:", dist)
}
}

package main

import(
"fmt"
)

constMaxWeight=1<<63-1// 最大权重，用于表示无穷大

typeNodestruct{
    id   int
    weight int
}

typeEdgestruct{
from, to int
    weight   int
}

func (n *Node)GetWeight()int{
return n.weight
}

func (n *Node)SetWeight(w int){
    n.weight = w
}

func BellmanFord(nodes []*Node, edges []*Edge, sourceID int)bool{
    n :=len(nodes)
for i :=0; i < n-1; i++{
for _, edge :=range edges {
            u, v := edge.from, edge.to
if nodes[u].GetWeight()!=MaxWeight&& nodes[v].GetWeight()> nodes[u].GetWeight()+edge.weight {
                nodes[v].SetWeight(nodes[u].GetWeight()+ edge.weight)
}
}
}

// Check for negative-weight cycles
for _, edge :=range edges {
        u, v := edge.from, edge.to
if nodes[u].GetWeight()!=MaxWeight&& nodes[v].GetWeight()> nodes[u].GetWeight()+edge.weight {
returnfalse// Negative-weight cycle detected
}
}

// Check if all nodes are reachable
for _, node :=range nodes {
if node.GetWeight()==MaxWeight{
returnfalse// Unreachable node detected
}
}

returntrue// Feasible solution found
}

func main(){
    nodes :=[]*Node{
{0,0},// Source node
{1,MaxWeight},
{2,MaxWeight},
}
    edges :=[]*Edge{
{0,1,4},
{0,2,3},
{1,2,1},
}

ifBellmanFord(nodes, edges,0){
        fmt.Println("Feasible solution found")
}else{
        fmt.Println("No feasible solution")
}
}

package main

import(
"fmt"
"math"
)

typeEdgestruct{
    to     int
    weight int
}

func BellmanFord(edges [][]Edge, source int, n int)([]int,bool){
    dist :=make([]int, n)
for i :=range dist {
        dist[i]= math.MaxInt32
}
    dist[source]=0

for i :=0; i < n-1; i++{
for u :=0; u < n; u++{
for _, edge :=range edges[u]{
                v := edge.to
                w := edge.weight
if dist[u]+w < dist[v]{
                    dist[v]= dist[u]+ w
}
}
}
}

// Check for negative-weight cycles
for u :=0; u < n; u++{
for _, edge :=range edges[u]{
            v := edge.to
            w := edge.weight
if dist[u]+w < dist[v]{
returnnil,true// Negative cycle found
}
}
}

return dist,false
}

func main(){
// Example constraints
    constraints :=[][]int{
{0,1,3},// x1 - x0 <= 3
{1,2,-2},// x2 - x1 <= -2
{0,2,1},// x2 - x0 <= 1
}

    n :=3// Number of variables
    edges :=make([][]Edge, n)
for _, constraint :=range constraints {
        u := constraint[0]
        v := constraint[1]
        w := constraint[2]
        edges[u]=append(edges[u],Edge{v, w})
}

    source :=0// Arbitrary choice for source node
    dist, hasNegativeCycle :=BellmanFord(edges, source, n)

if hasNegativeCycle {
        fmt.Println("The system has a negative-weight cycle.")
}else{
        fmt.Println("Distances from source node:", dist)
}
}