// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
}
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// Skip stale entries left over from an earlier, longer path.
}
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// Skip stale entries left over from an earlier, longer path.
if cur.dist > dist[cur.node] {
continue
}
}
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// Skip stale entries left over from an earlier, longer path.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: can we reach it faster through cur?
}
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// Skip stale entries left over from an earlier, longer path.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: can we reach it faster through cur?
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist
}
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// Skip stale entries left over from an earlier, longer path.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: can we reach it faster through cur?
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
}
// Item and PriorityQueue implement container/heap as a min-heap on dist.
// graph[node] = list of outgoing edges. Edge weights must be non-negative.
type Edge struct {
to, weight int
}
func dijkstra(graph [][]Edge, src int) []int {
// Micropattern: best-known distance to each node, source at 0.
const inf = int(1e18)
dist := make([]int, len(graph))
for i := range dist {
dist[i] = inf
}
dist[src] = 0
// Min-heap of (node, dist), always popping the closest frontier node.
pq := &PriorityQueue{{node: src, dist: 0}}
for pq.Len() > 0 {
cur := heap.Pop(pq).(Item)
// Skip stale entries left over from an earlier, longer path.
if cur.dist > dist[cur.node] {
continue
}
// Relax each neighbor: can we reach it faster through cur?
for _, e := range graph[cur.node] {
if nd := cur.dist + e.weight; nd < dist[e.to] {
dist[e.to] = nd
heap.Push(pq, Item{node: e.to, dist: nd})
}
}
}
return dist // O((V + E) log V)
}
// Item and PriorityQueue implement container/heap as a min-heap on dist.
type Item struct {
node, dist int
}
type PriorityQueue []Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].dist < pq[j].dist }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x any) { *pq = append(*pq, x.(Item)) }
func (pq *PriorityQueue) Pop() any {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[:n-1]
return item
}
Tap the left half to go back, the right half to go forward.
Arrow keys or space to navigate · Esc to exit.