SGT

1

graph LR;
	b-->c;
	c-->g;
	g-->u;
	u-->a;
	a-->b;

Since $C$ is a cycle, every vertex that appears as the start vertex $u$ of an edge also appears as the end vertex $v$ of another edge, except for the sequence which cycles back to the start. Thus, when summing $h(u)-h(v)$, these values will cancel out.

2

b-->|3|c;
c-5e
e3f
f1g
...

thing going from one thing to all others

They will stay the same.

3

(a)

1-3->2 1-2->3 1-4->5 2-7->5 2-1->4 5-6->4 4-2->1 3-4->2 4-5->3

If all edge weights are non-neg, then for each vertex v , shortest from s to v in graph g’ is equal to 0

thus h(v) = 0, for each vertex, so all new edge weights are the same as the input graph

(b)

s to all nodes is 0

relaxation-technique init: relax is applied to all $n$ edges outgoing from $s$ in $G$

when a vertex $u$ is taken from queue, all edges outgoing from $u$ are relaxed relax operation is applied exactly once to each edge

4

(a)

1—>2 s—>2 2—>3 2-0->4 4—>3 1-(-3)->5 5-(infinity)->1 (becomes)

example: s-(-2)->a x-7->s x-2->u x-3->v v-(-2)->u u-1->a v-5->a

(b)

ok

5