Eulerian paths, Hamiltonian cycles, and shortest paths
Can you trace every edge of a graph without lifting your pen? Can you visit every vertex exactly once? The questions sound alike, but one is easy and the other is famously hard.
Click two vertices to toggle an edge, or load an example, then press Find Path. Red vertices have odd degree: their count decides whether a path or circuit exists.
Click two vertices to toggle an edge
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.
An Eulerian path visits every edge exactly once. In a connected graph, 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.
Click vertices to build a path that visits each one exactly once, then press Run Backtracking and watch the search try ordering after ordering.
Click vertices to build a path visiting each exactly once
A Hamiltonian path visits every vertex exactly once. Unlike Eulerian paths, no simple existence criterion is known. 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.
Complexity contrast -- Eulerian path existence is O(V + E) to check, while Hamiltonian path existence requires exponential search in the worst case
Choose a source and a target vertex, then press Run Dijkstra. Watch it settle the closest unvisited vertex at every step.
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. 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.
Spot a mistake or have an idea?