DFS Topological Sort and Shorstest Path Problem

Question 1

Topological Sort

Answer 1

• Topological sort
• DFS can be used to perform a topological sort of a directed acyclic graph
• A topological sort of a DAG is a linear ordering of all its vertices such that if DAG contains an edge (u, v), then u appears before v in ordering

Question 2

Topological Sort Wotk

Answer 2

• Don’t need to sort by finish times

– Can just output vertices as they are finished and understand that we want the reverse of this list

Question 3

Shortest path problem examples

Answer 3

• Airlineflighttimes
• Telephonecommunicationcosts
• Computernetworksresponsetimes • Fastestwaytogettoschoolbycar

Question 4

Single-source shortest path

Answer 4

Find a shortest path from a given source (vertex s) to each of the vertices. Dijkstra’s algorithm.

Question 5

Single-pair shortest path

Answer 5

Given two vertices, find a shortest path between them.

Question 6

All-pairs shortest path

Answer 6

Find shortest-paths for every pair of vertices.

Question 7

Shortest path problem definition #1

Answer 7

• Definition 1: Given a path p=v1 →v2 →…→vk , the weight of the path is the sum of the weights of all its edges

Question 8

Shortest path problem definition #2

Answer 8

• Definition 2: The shortest path weight from u to v is defined
by:

δ(u,v)=% {()$min w p : p path from u to v if there is a path from u to v

∞ otherwise

Question 9

Shortest path problem definition #3

Answer 9

A shortest path from vertex u to vertex v is defined as any path p with weight w(p)= δ(u,v)

Question 10

Dijkstra’s algorithm

Answer 10

Assumptions:
– Directed or undirected graph
– All edges must have nonnegative weights
– Connected graph

• Input: Weighted graph G=(E,V) and source vertex v∈V

•Output: Lengths of shortest paths from a given source
vertex v ∈ V to all other vertices
–
With slight modification we can obtain the path

Question 11

Dijkstra’s algorithm running time

Answer 11

|V|Time-extract-min + |E|Time-Decrease-key

Question 12

Greedy Algorithm

Answer 12

•Dijkstra’s algorithm uses a greedy strategy for designing algorithms

• Greedy approach
– In order to get what you want just start grabbing what looks best

• Shortest path we wish to find the path with lowest weight
• It always chooses the lightest vertex

Question 13

Topological Sort Algorithm

Answer 13

TOPOLOGICAL-SORT(G)
call DFS(G) to compute finishing time for each vertex v
as each vertex is finished, insert it onto the front of a linked list
return linked list

Can just output vertices as they are finished and understand that we want the reverse of this list

• Space:O(V+E) • Time:O(V+E)