In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized. Dijkstra’s algorithm For a given vertex called the source in a weighted connected graph, Dijkstra’s Algorithm can find the shortest paths to all the graph’s other vertices. This algorithm is applicable to both undirected … Continue reading "[Algorithm 101] Shortest Path Problem"

Read More# Tag: graph-theory

## [Algorithm 101] Topological Sorting

A directed acyclic graph (DAG) is not only necessary but also sufficient for topological sorting to be possible. DFS Perform a DFS traversal and note the order in which vertices become dead-ends (i.e., popped off the traversal stack). Reversing this order yields a solution to the topological sorting problem, provided, of course, no back edge has been encountered … Continue reading "[Algorithm 101] Topological Sorting"

Read More