Use Case Scenario Flashcards
Name graph algorithms that are used for:
Traversing a Graph
DFS, Explore, BFS
Name graph algorithms that are used for:
Getting Components
SCC
Name graph algorithms that are used for:
Getting Shortest Paths
Dijkstra’s, Bellman Ford, Floyd Warshall
Name graph algorithm that are used for:
Finding MSTs
Kruskal’s, Prims
Name graph algorithm that are used for:
finding an existing path
2-SAT
Name graph algorithms that are used for:
Finding the Max Flow
Ford-Fulkerson
Edmonds-Karp
What is the best algorithm for determining the shortest path of graph G that is weighted with positive weights?
Djikstra’s
What are the best algorithms for determining the shortest path of graph G that is weighted with negative weights?
Bellman Ford or Floyd Warshall
What are the best algorithms for determining the best capacity?
Ford-Fulkerson and Edmonds-Karp
What is the best algorithm to convert a graph to a topologically sorted DAG?
SCC
What is the best algorithm to find the shortest path from all vertices of a directed, weighted graph with negative weights?
Floyd Warshall
What is the best algorithm to find the shortest path from a given vertex of a directed, weighted graph with negative weights?
Bellman Ford
What is the best algorithm to remove cycles in a directed graph?
SCC
What is the best algorithm to determine the max flow of a graph with positive integers capacities?
Ford-Fulkerson
What is the best algorithm to determine the max flow of a graph with non-integer capacities?
Edmond-Karp
