Shortest Path Algorithms

Shortest path algorithms are fundamental in graph theory and are widely used in various applications such as network routing, geographical mapping, and transportation planning. Here, we'll discuss the implementations of three classic shortest path algorithms: Dijkstra's algorithm, Bellman-Ford algorithm, and Floyd-Warshall algorithm.

1. Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted graph with non-negative weights.

Implementation:

go
package main

import (
	"container/heap"
	"fmt"
	"math"
)

// An Item is something we manage in a priority queue.
type Item struct {
	node     int
	priority int
	index    int
}

// A PriorityQueue implements heap.Interface and holds Items.
type PriorityQueue []*Item

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
	return pq[i].priority < pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
	pq[i].index = i
	pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
	n := len(*pq)
	item := x.(*Item)
	item.index = n
	*pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*pq = old[0 : n-1]
	return item
}

func (pq *PriorityQueue) update(item *Item, priority int) {
	item.priority = priority
	heap.Fix(pq, item.index)
}

func dijkstra(graph map[int]map[int]int, start int) map[int]int {
	dist := make(map[int]int)
	for node := range graph {
		dist[node] = math.MaxInt32
	}
	dist[start] = 0

	pq := make(PriorityQueue, 0)
	heap.Init(&pq)
	heap.Push(&pq, &Item{node: start, priority: 0})

	for pq.Len() > 0 {
		u := heap.Pop(&pq).(*Item).node

		for v, weight := range graph[u] {
			if dist[u]+weight < dist[v] {
				dist[v] = dist[u] + weight
				heap.Push(&pq, &Item{node: v, priority: dist[v]})
			}
		}
	}

	return dist
}

func main() {
	graph := map[int]map[int]int{
		0: {1: 4, 2: 1},
		1: {3: 1},
		2: {1: 2, 3: 5},
		3: {},
	}
	start := 0
	distances := dijkstra(graph, start)
	for node, distance := range distances {
		fmt.Printf("Distance from %d to %d: %d\n", start, node, distance)
	}
}

2. Bellman-Ford Algorithm

The Bellman-Ford algorithm computes the shortest paths from a single source vertex to all other vertices in a weighted graph. It can handle graphs with negative weights and detects negative weight cycles.

Implementation:

go
package main

import (
	"fmt"
	"math"
)

type Edge struct {
	u, v, weight int
}

func bellmanFord(edges []Edge, V, start int) (map[int]int, bool) {
	dist := make(map[int]int)
	for i := 0; i < V; i++ {
		dist[i] = math.MaxInt32
	}
	dist[start] = 0

	for i := 1; i < V; i++ {
		for _, edge := range edges {
			u, v, weight := edge.u, edge.v, edge.weight
			if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
				dist[v] = dist[u] + weight
			}
		}
	}

	for _, edge := range edges {
		u, v, weight := edge.u, edge.v, edge.weight
		if dist[u] != math.MaxInt32 && dist[u]+weight < dist[v] {
			return dist, false // Negative weight cycle detected
		}
	}

	return dist, true
}

func main() {
	edges := []Edge{
		{0, 1, -1}, {0, 2, 4}, {1, 2, 3}, {1, 3, 2}, {1, 4, 2},
		{3, 2, 5}, {3, 1, 1}, {4, 3, -3},
	}
	V := 5
	start := 0
	distances, ok := bellmanFord(edges, V, start)
	if !ok {
		fmt.Println("Graph contains a negative weight cycle")
	} else {
		for node, distance := range distances {
			fmt.Printf("Distance from %d to %d: %d\n", start, node, distance)
		}
	}
}

3. Floyd-Warshall Algorithm

The Floyd-Warshall algorithm finds shortest paths between all pairs of vertices in a weighted graph. It can handle negative weights but not negative weight cycles.

Implementation:

go
package main

import (
	"fmt"
	"math"
)

func floydWarshall(graph [][]int) [][]int {
	V := len(graph)
	dist := make([][]int, V)
	for i := range dist {
		dist[i] = make([]int, V)
		copy(dist[i], graph[i])
	}

	for k := 0; k < V; k++ {
		for i := 0; i < V; i++ {
			for j := 0; j < V; j++ {
				if dist[i][k] != math.MaxInt32 && dist[k][j] != math.MaxInt32 && dist[i][k]+dist[k][j] < dist[i][j] {
					dist[i][j] = dist[i][k] + dist[k][j]
				}
			}
		}
	}

	return dist
}

func main() {
	const INF = math.MaxInt32
	graph := [][]int{
		{0, 3, INF, INF},
		{2, 0, INF, INF},
		{INF, 7, 0, 1},
		{6, INF, INF, 0},
	}
	distances := floydWarshall(graph)
	for i := range distances {
		for j := range distances[i] {
			if distances[i][j] == INF {
				fmt.Print("INF ")
			} else {
				fmt.Printf("%d ", distances[i][j])
			}
		}
		fmt.Println()
	}
}

Summary

• Dijkstra's Algorithm: Efficient for graphs with non-negative weights, using a priority queue for optimization.
• Bellman-Ford Algorithm: Handles graphs with negative weights and detects negative weight cycles, though less efficient than Dijkstra's.
• Floyd-Warshall Algorithm: Computes shortest paths between all pairs of vertices, handling negative weights but not negative weight cycles.

These algorithms cover a broad range of use cases for shortest path computations in graphs, from single-source to all-pairs shortest paths, making them essential tools in a Go developer's toolkit.