single-source shortest paths

Question 1

What is the primary purpose of shortest-path algorithms?

Answer 1

To find the shortest path between nodes in a graph.

Question 2

True or False: Dijkstra’s algorithm can handle negative weight edges.

Answer 2

False.

Question 3

Fill in the blank: The __________ algorithm is used for finding the shortest paths from a single source vertex to all other vertices in a graph with negative weight edges.

Answer 3

Bellman-Ford

Question 4

Which algorithm is generally more efficient for graphs with non-negative weights, Dijkstra’s or Bellman-Ford?

Answer 4

Dijkstra’s algorithm.

Question 5

What is the time complexity of Dijkstra’s algorithm using a priority queue?

Answer 5

O((V + E) log V), where V is the number of vertices and E is the number of edges.

Question 6

what is the psduecode for bellman ford

Answer 6

BELLMAN-FORD.G; w; s/
1 INITIALIZE-SINGLE-SOURCE.G; s/
2 for i D 1 to jG:Vj 1
3 for each edge .u; / 2 G:E
4 RELAX.u; ; w/
5 for each edge .u; / 2 G:E
6 if :d > u:d C w.u; /
7 return FALSE
8 return TRUE

Question 7

I Eat Really Cold Ice For Good

Answer 7

“I Eat Really Cold Ice For Good “

Breakdown:

I — Initialize single source

E — Edges loop |V| - 1 times

R — Relax each edge

C — Check for negative cycles

I — If d[v] > d[u] + w(u,v)

F — False → negative cycle

V — Valid path → no neg cycle

G — Good to return TRUE

T — Termination success

Question 8

what is the pedosocde for INITIALIZE-SINGLE-SOURCE

Answer 8

INITIALIZE-SINGLE-SOURCE.G; s/
1 for each vertex v E G.V
v.d = infity
v.pi =NIL
s.d = 0

Question 9

path relaztion proof

Answer 9

=[=p—

Question 9

what is the pedosocde for Relax ?

Answer 9

RELAX(u,v,w)
if v.d > u.d +w(u,v)
v.d = u.d+w(u,v)
v.pi=u

Question 10

psdeocode for dag shirest path

Answer 10

DAG-SHORTEST-PATH(G,w,s)
topologically sort the vertices
INIT-SINGLE-SOURCE(G,s)
for each vertex u, taken in topicallay sorted order
for each vertex v E G.adj[u]
relax(u,v,w)

Question 11

corretness for dag shirtest path

Answer 11

• becausse we process vertices in topoglovally sorted order,edges of any path must be relaxed in order of appearance in the path.
• edges on any shortest path are relaxed in order

by path relaztio theroem, correct

Question 12

psedocode for dikstra algoritm

Answer 12

DIJKSTRA(G, w, s):
INITIALIZE-SINGLE-SOURCE(G, s)
S = {} // The set of processed vertices
Q = G:V // The priority queue with all vertices
while Q ≠ ∅:
u = EXTRACT-MIN(Q) // Extract the vertex with the minimum distance
S = S ∪ {u} // Add u to the set of processed vertices
for each v ∈ G:Adj[u]:
RELAX(u,v,w) // Relaxation step

Question 13

do example on page 680