Spanning trees & more shortest paths

package main
 
import (
	"container/heap"
	"fmt"
)
 
type edge struct{ to, w int }
type item struct{ w, to, from int }
type pq []item
 
func (p pq) Len() int           { return len(p) }
func (p pq) Less(i, j int) bool { return p[i].w < p[j].w }
func (p pq) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p *pq) Push(x any)        { *p = append(*p, x.(item)) }
func (p *pq) Pop() any {
	old := *p
	x := old[len(old)-1]
	*p = old[:len(old)-1]
	return x
}
 
func prim(adj [][]edge) (int, [][2]int) {
	inTree := make([]bool, len(adj))
	h := &pq{{0, 0, -1}} // start from node 0 with a free "edge"
	total := 0
	var used [][2]int
	for h.Len() > 0 {
		it := heap.Pop(h).(item)
		if inTree[it.to] {
			continue // a cheaper edge already brought this node in
		}
		inTree[it.to] = true
		total += it.w
		if it.from >= 0 {
			used = append(used, [2]int{it.from, it.to})
		}
		for _, e := range adj[it.to] {
			if !inTree[e.to] {
				heap.Push(h, item{e.w, e.to, it.to})
			}
		}
	}
	return total, used
}
 
func main() {
	// A=0 B=1 C=2 D=3 E=4, the same graph as the Kruskal visualizer
	edges := [][3]int{{0, 1, 4}, {0, 2, 1}, {1, 2, 2}, {1, 3, 5}, {2, 3, 8}, {3, 4, 3}, {2, 4, 9}}
	adj := make([][]edge, 5)
	for _, e := range edges {
		adj[e[0]] = append(adj[e[0]], edge{e[1], e[2]})
		adj[e[1]] = append(adj[e[1]], edge{e[0], e[2]})
	}
	total, used := prim(adj)
	fmt.Println("MST weight:", total)
	name := "ABCDE"
	for _, u := range used {
		fmt.Printf("  %c-%c\n", name[u[0]], name[u[1]])
	}
}

MST weight: 11
  A-C
  C-B
  B-D
  D-E

package main
 
import (
	"fmt"
	"math"
)
 
type Edge struct{ U, V, W int }
 
const inf = math.MaxInt / 2 // big, but safe to add to
 
func bellmanFord(n int, edges []Edge, src int) ([]int, bool) {
	dist := make([]int, n)
	for i := range dist {
		dist[i] = inf
	}
	dist[src] = 0
	for round := 1; round <= n-1; round++ {
		changed := false
		for _, e := range edges {
			if dist[e.U] != inf && dist[e.U]+e.W < dist[e.V] {
				dist[e.V] = dist[e.U] + e.W
				changed = true
			}
		}
		fmt.Printf("  after round %d: %v\n", round, show(dist))
		if !changed {
			break // already stable: stop early
		}
	}
	for _, e := range edges { // the extra round
		if dist[e.U] != inf && dist[e.U]+e.W < dist[e.V] {
			return dist, false
		}
	}
	return dist, true
}
 
func show(d []int) []string {
	out := make([]string, len(d))
	for i, x := range d {
		if x == inf {
			out[i] = "∞"
		} else {
			out[i] = fmt.Sprint(x)
		}
	}
	return out
}
 
func main() {
	edges := []Edge{{0, 1, 4}, {0, 2, 5}, {1, 3, 3}, {2, 1, -3}, {3, 4, 2}}
	fmt.Println("with a negative edge 2->1 (-3):")
	dist, ok := bellmanFord(5, edges, 0)
	fmt.Println("  ok:", ok, "dist:", show(dist))
 
	cyc := append(edges, Edge{4, 2, -6}) // 2 -> 1 -> 3 -> 4 -> 2 sums to -4
	fmt.Println("with a negative cycle:")
	_, ok = bellmanFord(5, cyc, 0)
	fmt.Println("  ok:", ok)
}

with a negative edge 2->1 (-3):
  after round 1: [0 2 5 7 9]
  after round 2: [0 2 5 5 7]
  after round 3: [0 2 5 5 7]
  ok: true dist: [0 2 5 5 7]
with a negative cycle:
  after round 1: [0 2 3 7 9]
  after round 2: [0 0 1 5 7]
  after round 3: [0 -2 -1 3 5]
  after round 4: [0 -4 -3 1 3]
  ok: false

for k := range n {        // allow k as an intermediate stop
	for i := range n {
		for j := range n {
			dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
		}
	}
}

package main
 
import (
	"fmt"
	"math"
)
 
const inf = math.MaxInt / 2
 
func show(row []int) []string {
	out := make([]string, len(row))
	for i, x := range row {
		out[i] = fmt.Sprint(x)
		if x >= inf {
			out[i] = "∞"
		}
	}
	return out
}
 
func main() {
	n := 4
	dist := make([][]int, n)
	for i := range dist {
		dist[i] = make([]int, n)
		for j := range dist[i] {
			if i != j {
				dist[i][j] = inf
			}
		}
	}
	for _, e := range [][3]int{{0, 1, 3}, {1, 2, 1}, {2, 3, 2}, {0, 3, 10}, {3, 0, 1}} {
		dist[e[0]][e[1]] = e[2] // directed edges
	}
	for k := range n {
		for i := range n {
			for j := range n {
				dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
			}
		}
		fmt.Printf("allowing stops 0..%d: row 0 = %v\n", k, show(dist[0]))
	}
	fmt.Println("full matrix:")
	for _, row := range dist {
		fmt.Println(" ", row)
	}
}

allowing stops 0..0: row 0 = [0 3 ∞ 10]
allowing stops 0..1: row 0 = [0 3 4 10]
allowing stops 0..2: row 0 = [0 3 4 6]
allowing stops 0..3: row 0 = [0 3 4 6]
full matrix:
  [0 3 4 6]
  [4 0 1 3]
  [3 6 0 2]
  [1 4 5 0]

package main
 
import "fmt"
 
// Minimum walls (#) to break to get from the top-left to the bottom-right.
func minBreaks(grid []string) int {
	R, C := len(grid), len(grid[0])
	dist := make([][]int, R)
	for i := range dist {
		dist[i] = make([]int, C)
		for j := range dist[i] {
			dist[i][j] = -1
		}
	}
	type cell struct{ r, c int }
	dq := []cell{{0, 0}}
	dist[0][0] = 0
	for len(dq) > 0 {
		cur := dq[0]
		dq = dq[1:]
		for _, d := range []cell{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} {
			nr, nc := cur.r+d.r, cur.c+d.c
			if nr < 0 || nc < 0 || nr >= R || nc >= C {
				continue
			}
			w := 0
			if grid[nr][nc] == '#' {
				w = 1 // breaking a wall costs 1
			}
			nd := dist[cur.r][cur.c] + w
			if dist[nr][nc] == -1 || nd < dist[nr][nc] {
				dist[nr][nc] = nd
				if w == 0 {
					dq = append([]cell{{nr, nc}}, dq...) // same distance: front
				} else {
					dq = append(dq, cell{nr, nc}) // one more: back
				}
			}
		}
	}
	return dist[R-1][C-1]
}
 
func main() {
	fmt.Println(minBreaks([]string{
		"..#..",
		"###.#",
		"..#..",
		".####",
		"....#",
	}))
	fmt.Println(minBreaks([]string{"..", ".."}))
}

2
0