Table of Contents

Topological Sort

• The topological sort of a graph is a list of nodes in the graph, sorted so that the starting node of every edge appears before the destination node.
  • If an edge goes from nodes A → B, then A appears before B in the topological sort. This will be true for every pair of nodes in every edge in the graph.
• Requirements for a graph to have a topological sort:
  1. Directed (edges have direction).
  2. Acyclic (no looped paths).
• Algorithm:
  1. Go through the graph. Check whether each node has incoming edges.
  2. If a node has no incoming edges:
     1. Add the node to the bottom of the topological sort.
     2. Delete the node’s outgoing edges from the graph.
  3. Repeat until no more nodes can be added to the topological sort.

Dijkstra’s Algorithm

• Dijkstra’s algorithm finds the shortest path from the starting node to every other node on the graph.
  • BFS/DFS also find the shortest path between nodes, but those don’t work on weighted graphs.
  • Weight = cost = distance between nodes.
• Requirements to use Dijkstra’s algorithm
  • The graph must not have negative edge costs.
• Efficiency - $O(E*LogV)$
  • For dense graphs, Dijkstra’s algorithm is efficient.
  • For sparse graphs (only a few edges around each node), it’s only efficient if you implement it using a priority queue to store the distances.