bellman_ford.go

package main

import (
	"fmt"
	"math"
)

func bellmanFord(graph map[string]map[string]float64, source string) (map[string]float64, map[string]string) {
	distances := make(map[string]float64)
	predecessors := make(map[string]string)

	for vertex := range graph {
		distances[vertex] = math.Inf(1)
		predecessors[vertex] = ""
	}
	distances[source] = 0

	for range graph {
		for vertex := range graph {
			for neighbor, weight := range graph[vertex] {
				if distances[vertex]+weight < distances[neighbor] {
					distances[neighbor] = distances[vertex] + weight
					predecessors[neighbor] = vertex
				}
			}
		}
	}

	for vertex := range graph {
		for neighbor, weight := range graph[vertex] {
			if distances[vertex]+weight < distances[neighbor] {
				panic("Negative-weight cycle detected")
			}
		}
	}

	return distances, predecessors
}

func main() {
	// Test data
	graph := map[string]map[string]float64{
		"A": {"B": -1, "C": 4},
		"B": {"C": 3, "D": 2, "E": 2},
		"C": {},
		"D": {"B": 1, "C": 5},
		"E": {"D": -3},
	}
	source := "A"

	// Run the algorithm
	distances, predecessors := bellmanFord(graph, source)

	// Expected output
	fmt.Println("Distances:", distances)
	fmt.Println("Predecessors:", predecessors)
  
  // Result
  // Distances: map[A:0 B:-1 C:2 D:-2 E:1]
  // Predecessors: map[A: B:B C:B D:E E:B]

}