Neural Sync Active

computationalthinking-week8

Registry Synced

computationalthinking-week8

530 words

3 min read

Reading compass

Now · Week map

Deep study for Quiz 2 week 8. Labels on edges carry weights, costs, or names — adjacency structures must store values, not just 0/1.

Week map

Unweighted vs labelled → weight matrix → multi-graph caution → shortest-path intuition → reading labelled diagrams.

Labelled edge notation

Label → data on edge → weight, distance, time, capacity.
Weighted graph → each edge has numeric label → often non-negative in intro problems.
$M[i][j] = w$ → edge from $i$ to $j$ has weight $w$ .
$M[i][j] = 0$ or $\infty$ → no edge (convention varies — read problem statement).

Mini-example: three cities 0, 1, 2. Direct roads: 0→1 weight 4, 1→2 weight 2, 0→2 weight 10.

(Adjust to matrix form in examples below.)

Weight matrix


text
W = [ 0  4 10]
    [ ∞  0  2]
    [ ∞  ∞  0]

Use ∞ or blank for missing edge.

W[0][1]=4

W[1][2]=2

. Path 0→1→2 has total weight

4+2=6

, better than direct 0→2 weight 10.

Adjacency list with labels

Alternative to matrix:


text
0 → [(1, 4), (2, 10)]
1 → [(2, 2)]
2 → []

Each entry (neighbor, weight). Space-efficient for sparse graphs.

Directed vs undirected weights

Undirected road length

w

\{i,j\}

→ typically

W[i][j] = W[j][i] = w

Directed → only one direction gets weight unless both stated.

Pattern families

Easy — Read label from diagram

Identify weight on edge between two named vertices. List all neighbors with weights from one vertex.

Medium — Build weight matrix

From edge list

(u, v, w)

fill

W[u][v]

. Handle missing edges with 0 or ∞ per convention.

Hard — Compare path totals

Sum weights along path. Compare two routes. Greedy “pick lightest edge next” may fail globally — but Quiz 2 often asks direct sum comparison only.

Worked mini-examples

Example 1 — Matrix fill.

Edges: (0,1,3), (1,2,5). Directed:


text
W[0][1]=3, W[1][2]=5, others missing

Example 2 — Path sum.

Path 0→1→2: weights 3 + 5 = 8.

Example 3 — Undirected symmetry.

Edge A—B weight 7 →

W[A][B]=W[B][A]=7

Example 4 — No edge.

W[2][0]

missing → no direct 2→0 edge in directed sense.

Example 5 — List form lookup.

From vertex 1 list [(0, 2), (2, 4)]: edge to 0 weight 2, to 2 weight 4.

Traps

Confusing “no edge” 0 with “zero weight” edge — problem defines convention.
Forgetting directed orientation when summing path.
Double-counting undirected edge in degree/weight tally.
Picking edge with min label locally vs min total path.
Vertex label mismatch with matrix index.

Diagnostic (try yourself)

Weighted edge from X to Y is 6. In matrix with X=1, Y=2, what is $W[1][2]$ ?
Path A→B→C with weights 3 and 5. Total weight?
Undirected edge weight 4 between vertices 0 and 2. What are $W[0][2]$ and $W[2][0]$ ?
Adjacency list for vertex 1 is [(2, 7), (3, 1)]. What is weight of edge 1→3?
Direct path weight 12 vs two-hop path 4+5. Which route is cheaper?