What is a shortest path?
A shortest path in a weighted digraph is the path with the smallest total weight from a source vertex to a destination vertex.
What is a shortest path tree (SPT)?
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.
What are the properties of shortest paths?
- Paths are directed
- Weights are not necessarily distances
- Not all vertices need to be reachable
- Algorithms ignore cycles
- Shortest paths are not necessarily unique
How are edges on the SPT represented?
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.
How is the distance to the source represented?
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.
What is edge relaxation?
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.
What is vertex relaxation?
Vertex relaxation involves considering all incoming edges to a vertex and updating the shortest distance based on the shortest distances of its neighboring vertices.
What is the importance of edge relaxation?
it is the primary method to update shortest path estimates and ensure they are minimized.
What is the process to relax an edge in Dijkstra’s algorithm?
In Dijkstra’s algorithm, to relax an edge, you update the shortest path estimate if the path through the edge is shorter.
What is the process of Dijkstra’s algorithm?
- Extract vertex with minimum distance v from s from pq.
- 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
What is the space time usage of Dijkstra’s?
Space = V
Time = E log V
Why does Djikstra’s not work on negative weights?
Assumption that adding edges will not decrease length and adding vertex SPT will mean it won’t change afterwards
Why can Djikstra’s not be used to find longest path?
Selecting node with largest distance may not necessarily lead to finding longest path because it might involve smaller distances
How do we find the shortest path in a DAG?
- Sort topologically
- Process each vertex in the sorted order
- For each vertex v and its adjacent vertices u:
* If current distance to u > distance to v + weight of vu, update distance to u
*
What is the time use of relaxing vertices in topological order for shortest and longest paths?
E + V
How do we find the longest path in a DAG?
- Sort topologically
- Set distances to all other vertices to negative infinity
- Process vertex in topological order
- 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.
What is the critical path method?
- Create DAG with source and sink
- Add edge from each job’s start vertex to end vertex
- For each precedence constraint v-> w, add zero-weight edge from end of task v to start of w
- Add zero-weight edge from source to start vertex of each job
- add zero-weight edges frfom end vertex to sink node
- Solve using the longest path algorithm for DAG
What are the restrictions for Dijkstra’s, topological sort and Bellman ford algorith?
- Positive edge weights
- Edge weighted DAGs
- No negative cycles
What are the worst case time performances for D, TS, and BF? What are their space uses?
- Elog V
- E + V
- VE (has typical of E +V)
V
What are the sweet spots for D, TS, BF?
- Worst-case guarantee
- Optimal for acyclic
- Widely applicable
