Eulerian paths, Hamiltonian cycles, and shortest paths
A path is a sequence of vertices connected by edges, while a cycle is a path that returns to its starting vertex. These concepts are fundamental to graph theory and lead to deep questions about traversing graphs efficiently.
Eulerian paths traverse every edge exactly once, and their existence can be checked with a simple degree condition. Hamiltonian paths visit every vertex exactly once, but deciding their existence is NP-complete. Dijkstra's algorithm finds shortest paths in weighted graphs using a greedy expansion strategy.
An Eulerian path visits every edge exactly once. Toggle edges by clicking pairs of vertices and observe how the odd-degree count determines whether a path or circuit exists. Red vertices indicate odd degree.
Click two vertices to toggle an edge
Key insight: An Eulerian circuit exists when all vertices have even degree. An Eulerian path exists when exactly two vertices have odd degree -- those two vertices become the start and end of the path.
A Hamiltonian path visits every vertex exactly once. Try building one manually by clicking vertices, or watch the backtracking algorithm systematically explore all possibilities. Unlike Eulerian paths, no simple existence criterion is known.
Click vertices to build a path visiting each exactly once
Key insight: Deciding whether a Hamiltonian path exists is NP-complete. The backtracking algorithm must potentially explore an exponential number of orderings, making the contrast with the efficiently-solvable Eulerian case especially striking.
Dijkstra's algorithm finds the shortest path between two vertices in a weighted graph. It greedily expands from the source, always processing the closest unvisited vertex. Select source and target vertices, then run the algorithm to watch it explore.
Key insight: Dijkstra's algorithm runs in O(V²) time with a simple array, or O((V + E) log V) with a priority queue. It requires all edge weights to be non-negative.