Algo: Graph

• A graph algorithm is a one that deals with answering questions that involve graphs.

• There are 6 significant graph algorithms: Dijkstra, Kruskal, Prim, Floyd-Warshall, Bellman-Ford, and Kahn’s Algorithm for Topological Sorting.

• The Minimum Spanning Tree(MST) of a graph is the tree that spans all the nodes of a weighted graph and whose sum of edge-weights is minimized.

Dijkstra's Algorithm

• Dijkstra's algorithm is an algorithm used to find the shortest distance between a node and another node in the same graph, and works only when all the edge-weights are positive.

Kruskal's Algorithm

• Kruskal's algorithm is greedy algorithm used to find the MST of a graph. It involves always selecting the minimum-cost edge that doesn't result in a cycle.

Prim's Algorithm

• Prim's algorithm is another greedy algorithm used to find the MST of a graph. It involves selecting the minimum cost edge, then the minimum cost-edge that is linked to that without forming a cycle, and so on.

Floyd-Warshall's Algorithm

• Floyd-Warshall's algorithm is a dynamic-programming algorithm used to find the shortest distances between each pair of nodes of a graph. It works for both positive and negative weights.

Bellman-Ford's Algorithm

• Bellman-Ford's algorithm is an algorithm used to achieve the same purpose as Djikstra's algorithm, but works for both positive and negative edge-weights. It can also be used to detect negative cycles, however if there is any negative cycle, the shortest-distance calculation will not work.

Kahn’s Algorithm for Topological Sorting

• Kahn’s algorithm for topological sorting is an algorithm used to get a topological sorting of a graph. For these graphs, each node is a dependency that needs to be fulfilled before moving onto its children. A topological sorting is the list of all the nodes of the graph in any ordering that meets all the node-dependency requirements.