Skip to content

Instantly share code, notes, and snippets.

@TheAlchemistKE
Created October 22, 2023 11:48
Show Gist options
  • Save TheAlchemistKE/b6cfb676523841244f41c6e2f6a13c15 to your computer and use it in GitHub Desktop.
Save TheAlchemistKE/b6cfb676523841244f41c6e2f6a13c15 to your computer and use it in GitHub Desktop.
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]
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment