Shortest Paths

Question 1

What is a shortest path?

Answer 1

A shortest path in a weighted digraph is the path with the smallest total weight from a source vertex to a destination vertex.

Question 2

What is a shortest path tree (SPT)?

Answer 2

An SPT is a subgraph containing the source vertex and all vertices reachable from it, forming a directed tree rooted at the source such that every tree path is a shortest path in the digraph.

Question 3

What are the properties of shortest paths?

Answer 3

• Paths are directed
• Weights are not necessarily distances
• Not all vertices need to be reachable
• Algorithms ignore cycles
• Shortest paths are not necessarily unique

Question 4

How are edges on the SPT represented?

Answer 4

Edges on the SPT are represented using a parent-edge representation in a vertex-index array ‘edgeTo[]’ of DirectedEdge objects, where edgeTo[v] is the edge connecting v to its parent.

Question 5

How is the distance to the source represented?

Answer 5

The distance to the source is represented by a vertex-indexed array ‘distTo[]’, where distTo[v] is the shortest known path from the source to v.

Question 6

What is edge relaxation?

Answer 6

Edge relaxation is the process of testing whether the best known way from the source to a vertex w is to go through another vertex v using the edge v-w. If this path is shorter, the data structures are updated.

Question 7

What is vertex relaxation?

Answer 7

Vertex relaxation involves considering all incoming edges to a vertex and updating the shortest distance based on the shortest distances of its neighboring vertices.

Question 8

What is the importance of edge relaxation?

Answer 8

it is the primary method to update shortest path estimates and ensure they are minimized.

Question 9

What is the process to relax an edge in Dijkstra’s algorithm?

Answer 9

In Dijkstra’s algorithm, to relax an edge, you update the shortest path estimate if the path through the edge is shorter.

Question 10

What is the process of Dijkstra’s algorithm?

Answer 10

1. Extract vertex with minimum distance v from s from pq.
2. For each neighbour u of v:
   * If current known distance to u > distance to v + weight of vu, update distance to u and change predecessor to v
   * If distance updated, insert v into PQ with new distance
   * Repeat under PQ empty

Question 11

What is the space time usage of Dijkstra’s?

Answer 11

Space = V
Time = E log V

Question 12

Why does Djikstra’s not work on negative weights?

Answer 12

Assumption that adding edges will not decrease length and adding vertex SPT will mean it won’t change afterwards

Question 13

Why can Djikstra’s not be used to find longest path?

Answer 13

Selecting node with largest distance may not necessarily lead to finding longest path because it might involve smaller distances

Question 14

How do we find the shortest path in a DAG?

Answer 14

1. Sort topologically
2. Process each vertex in the sorted order
3. For each vertex v and its adjacent vertices u:
   * If current distance to u > distance to v + weight of vu, update distance to u
   *

Question 15

What is the time use of relaxing vertices in topological order for shortest and longest paths?

Answer 15

E + V

Question 16

How do we find the longest path in a DAG?

Answer 16

1. Sort topologically
2. Set distances to all other vertices to negative infinity
3. Process vertex in topological order
4. For each vertex v and adjacent vertices u:
   * If distance to u is LESS than distance to v + weight of vu, update.

OR

Create copy of given DGA with negated edge weights. The shortest path in the copy is the longest path in the original. Negate the weights in the solution.

Question 17

What is the critical path method?

Answer 17

1. Create DAG with source and sink
2. Add edge from each job’s start vertex to end vertex
3. For each precedence constraint v-> w, add zero-weight edge from end of task v to start of w
4. Add zero-weight edge from source to start vertex of each job
5. add zero-weight edges frfom end vertex to sink node
6. Solve using the longest path algorithm for DAG

Question 18

What are the restrictions for Dijkstra’s, topological sort and Bellman ford algorith?

Answer 18

1. Positive edge weights
2. Edge weighted DAGs
3. No negative cycles

Question 19

What are the worst case time performances for D, TS, and BF? What are their space uses?

Answer 19

1. Elog V
2. E + V
3. VE (has typical of E +V)

V

Question 20

What are the sweet spots for D, TS, BF?

Answer 20

1. Worst-case guarantee
2. Optimal for acyclic
3. Widely applicable