Weighted Graphs — Programuoki

Code

wgraph.go — the skeleton

Create wgraph.go. The last skeleton in the course.

Most of it is code you have already written:

WGraph is lesson 14's Graph with one extra field on the edge;
BFSW is that same BFS, carried across unchanged;
NodeHeap is lesson 13's heap with a different payload. The same array-tree, the same 2i+1 and (i−1)/2, the same sift-up and sift-down. Only what sits in the array changed.

Genuinely new: DijkstraHeap and DijkstraScan.

Worth noting:

The counter counts FRONTIER work — every comparison the queue makes while choosing what comes next. In the heap that is the sift comparisons; in the linear scan it is every node looked at. It is the only quantity step 5 compares, and it is what transit's diagnostics report too.
Lazy deletion, not decrease-key. When a cheaper route appears, push the node again. When you pop a node that is already done, skip it.
Return settled too — how many nodes were finalised. Both versions must return the same number; if they do not, one of them is doing something else.
DijkstraScan is not to be fixed. It is slow on purpose.

Gotcha

Check if v == to when you pop, not when you push.

Return the path the moment to first enters the queue and you get the first route found, not the cheapest — because a cheaper one may still arrive. It is exactly the mistake lesson 14 made by marking seen in the wrong place, except that here it costs correctness rather than path length.

The heap's promise holds at the pop: only then is it known that nothing cheaper remains.

wgraph.go CREATE

Create this file in ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithm is in step 2; wgraph_test.go
// decides whether you got it right.
//
// The counter counts FRONTIER WORK — every comparison the queue makes while
// deciding what comes next. Not edges, not nodes. That is the quantity step 5
// compares between the two frontiers, and it is the one `transit` reports too.

// WEdge is lesson 14's edge with one field added: what it costs to use.
//
// Here the cost is DAYS BETWEEN BORROWS — how long a reader waited before
// picking up the next book. Lesson 14 treated every edge as one hop; now they
// are not interchangeable.
type WEdge struct {
	To   int32
	Cost int32
}

// WGraph is lesson 14's Graph with weights. Everything else — the adjacency
// list, the trails, the shape — is unchanged.
type WGraph struct {
	adj   [][]WEdge
	edges int
}

func NewWGraph(n int) *WGraph { panic("not implemented") }

func (g *WGraph) Nodes() int { panic("not implemented") }
func (g *WGraph) Edges() int { panic("not implemented") }

// AddEdge links a and b in both directions at the given cost, rejecting
// self-loops and duplicates as in lesson 14.
func (g *WGraph) AddEdge(a, b, cost int32) { panic("not implemented") }

func (g *WGraph) Neighbors(v int32) []WEdge { panic("not implemented") }

// NodeHeap is lesson 13's MinHeap with a different payload: it orders NODES by
// their tentative distance instead of items by Rating.
//
// The array-tree, the sift-up, the sift-down and the index arithmetic are the
// SAME CODE. Only what sits in the array changed — which is the point. Copy your
// heap across and change the payload; do not invent a second one.
//
// Two parallel slices rather than a slice of structs, so a swap touches two
// small arrays instead of copying a struct. Either works; this one is closer to
// what `transit` does.
type NodeHeap struct {
	node []int32
	dist []int32
}

func NewNodeHeap(capacity int) *NodeHeap { panic("not implemented") }

func (h *NodeHeap) Len() int { panic("not implemented") }

func (h *NodeHeap) Push(v, d int32, c *metrics.Counter) { panic("not implemented") }

// Pop returns the node with the smallest tentative distance.
func (h *NodeHeap) Pop(c *metrics.Counter) (node, dist int32, ok bool) {
	panic("not implemented")
}

// DijkstraHeap finds the CHEAPEST path, using the heap as the frontier.
//
// USE LAZY DELETION: when a cheaper route to a node appears, push it again
// rather than trying to update the entry already in the heap. Skip an entry
// whose node is already done. Step 2 explains why, and a test checks that you
// did it this way — a version with no stale entries is doing decrease-key, which
// is a different structure.
//
// Returns the path, its cost, and how many nodes were settled.
func DijkstraHeap(g *WGraph, from, to int32, c *metrics.Counter) ([]int32, int32, int, bool) {
	panic("not implemented")
}

// DijkstraScan is the same algorithm with no priority queue at all: to find the
// nearest unsettled node it looks at every node.
//
// It is CORRECT — the same path, the same cost. Do not "fix" it; step 5 is about
// what it costs, and a test requires both to agree.
func DijkstraScan(g *WGraph, from, to int32, c *metrics.Counter) ([]int32, int32, int, bool) {
	panic("not implemented")
}

// PathCost adds up the weights along a path, so a hop-count answer and a cost
// answer can be compared on the same footing.
func (g *WGraph) PathCost(path []int32) int32 { panic("not implemented") }

// BFSW is lesson 14's BFS on the weighted graph. It still counts HOPS and still
// ignores the weights entirely — copy it across unchanged. Step 1 is what that
// costs.
func BFSW(g *WGraph, from, to int32, c *metrics.Counter) ([]int32, bool) {
	panic("not implemented")
}