package main

import (
	"fmt"
	"math"
)

type graph struct {
	to int
	wt float64
}

func floydWarshall(g [][]graph) ([][]float64, [][][]int) {
	path := make([][][]int, len(g))
	dist := make([][]float64, len(g))
	for i := range dist {
		pi := make([][]int, len(g))
		di := make([]float64, len(g))
		for j := range di {
			di[j] = math.Inf(1)
			pi[j] = []int{}
		}
		di[i] = 0
		dist[i] = di
		path[i] = pi
	}
	for u, graphs := range g {
		for _, v := range graphs {
			dist[u][v.to] = v.wt
			path[u][v.to] = []int{u, v.to}
		}
	}
	for k, dk := range dist {
		pk := path[k]
		for i, di := range dist {
			pi := path[i]
			for j, dij := range di {
				if d := di[k] + dk[j]; dij > d {
					di[j] = d
					pi[j] = append(pi[k], pk[j][1:]...)
				}
			}
		}
	}
	return dist, path
}

func main() {
	gra := [][]graph{
		1: {{2, 3}, {3, 8}, {5, -4}},
		2: {{4, 1}, {5, 7}},
		3: {{2, 4}},
		4: {{1, 2}, {3, -5}},
		5: {{4, 6}},
	}

	dist, path := floydWarshall(gra)
	//dist[][] will be the output matrix that will finally
	//have the shortest distances between every pair of vertices
	for i, di := range dist {
		pi := path[i]
		s := ""
		for j, pij := range pi {
			if j > 0 {
				s += " "
			}
			s += fmt.Sprintf("%4g %-12s", di[j], fmt.Sprint(pij))
		}
		fmt.Printf("[%s]\n", s)
	}
}