Graph

Edsger Wybe Dijkstra

“The “Floyd-Warshall algorithm” is an algorithm for finding the shortest path between all pairs of vertices in a graph.”

“The “Bellman-Ford algorithm” is an algorithm for finding the shortest path between a single source vertex and all other vertices in a graph, even if the graph contains negative edge weights.”

“The “Johnson algorithm” is an algorithm for finding the shortest path between all pairs of vertices in a graph, even if the graph contains negative edge weights.”

Runtime Complexity

lookup append insert delete

Space Complexity

Hamiltonian Cycle

A Hamiltonian cycle (or circuit) is a Hamiltonian path such that there is an edge from the last vertex to the first vertex of the Hamiltonian path.

A Hamiltonian path in an undirected graph is a path that visits each vertex exactly once.

corresponds to: given a directed graph, find a simple cycle that contains each vertex in V

the simple cycle just needs to contain each vertex in V

determining whether a specific given cycle is Hamiltonian cycle or not is simple, you just have to traverse the cycle and touch all of the vertices exactly once

but determining whether or not the graph has a Hamiltonian cycle is a hard problem

A Hamiltonian circuit must start and end on the same vertex but a Hamiltonian path does not

Hamiltonian cycle is a NP-complete problem

Network Flow

shortest path \(O(v^2)\)

Graph Representation / Implementation

Edge list

Adjacency list

Adjacency matrix

Minimum Spanning Tree

“The “Prim’s algorithm” is an algorithm for finding a minimum spanning tree in a graph, which is a tree that connects all the vertices of the graph with the minimum total weight.”

“The “Kruskal’s algorithm” is another algorithm for finding a minimum spanning tree in a graph.”