SGT

1

x	d[x]	parent[x]
s	0	-
a	inf	-
b	inf	-
c	inf	-
d	inf	-

Visit s

x	d[x]	parent[x]
s	0	-
a	4	s
b	8	s
c	7	s
d	inf	-

Visit a

x	d[x]	parent[x]
s	0	-
a	4	s
b	8	s
c	7	s
d	12	a

Visit c

x	d[x]	parent[x]
s	0	-
a	4	s
b	8	s
c	7	s
d	11	c

Visit b

x	d[x]	parent[x]
s	0	-
a	2	b
b	8	s
c	7	s
d	11	c

Visit d

x	d[x]	parent[x]
s	0	-
a	2	b
b	8	s
c	7	s
d	11	c

Shortest path computed is 11 via s,c,d.

2. [..]
3. We can do a topological sort before running Dijkstra’s (no negative cycle) Or we can re-add nodes into the priority queue whenever we handle a negative edge
4. Exponential running time

2

Create a list L, keep removing ‘roots’ until graph is empty.

a->b, a->c, b->d

• Remove a
• Remove b
• Remove c
• Remove d

Therefore, a,b,c,d.

3

s,b,f,h,a,e,g,c,k,d

4

s,b,a,k,h,c,d,e,f,g

5

Q = (s) Visit s

x	d[x]	parent[x]
s	0	-
u	-2	s
v	inf	-
x	5	s
y	inf	-

Q = (u,x) Visit u

x	d[x]	parent[x]
s	0	-
u	-2	s
v	-1	u
x	4	u
y	inf	-

Q = (x,v) Visit x

x	d[x]	parent[x]
s	0	-
u	-2	s
v	-1	u
x	4	u
y	6	x

Q = (v,y) Visit v

x	d[x]	parent[x]
s	0	-
u	-2	s
v	-1	u
x	-6	v
y	3	v

Q = (y,x) Visit y

x	d[x]	parent[x]
s	0	-
u	-2	s
v	-1	u
x	-6	v
y	3	v

Q = (x) Visit x

x	d[x]	parent[x]
s	0	-
u	-3	s
v	-1	u
x	-6	v
y	3	v

Q = (y) Visit y

x	d[x]	parent[x]
s	0	-
u	-3	s
v	-1	u
x	-6	v
y	-4	x

Q = ()