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 fascinating questions about traversing graphs efficiently.
In this section, you'll learn the difference between Eulerian and Hamiltonian paths, and discover Dijkstra's famous algorithm for finding shortest paths in weighted graphs!
An Eulerian path visits every edge exactly once. Click vertices to add/remove edges and see when a path exists. Red vertices have odd degree!
Click two vertices to toggle an edge
A Hamiltonian path visits every vertex exactly once. Click vertices to try building one yourself, or watch the backtracking algorithm search!
Click vertices to build a path visiting each exactly once
Dijkstra's algorithm finds the shortest path between two vertices in a weighted graph. Watch it explore outward from the source, always choosing the closest unvisited vertex!
Time complexity: O(V² ) or O((V + E) log V) with priority queue
1. Königsberg Bridges: Euler proved in 1736 that crossing all 7 bridges exactly once is impossible. This problem founded graph theory and introduced the concept of vertex degree.
2. Eulerian Paths: A path that visits every edge exactly once. Exists only when the graph has 0 or 2 vertices of odd degree. An Eulerian circuit (returns to start) requires all vertices to have even degree.
3. Hamiltonian Paths: A path that visits every vertex exactly once. Unlike Eulerian paths, there's no simple criterion to check—the problem is NP-complete! We must use backtracking or other search algorithms.
4. Dijkstra's Algorithm: A greedy algorithm that finds shortest paths in weighted graphs. It maintains distances to all vertices and always processes the closest unvisited vertex next.
Next Up: In the next section, you'll learn about graph coloring — including chromatic numbers, map coloring, and the famous four-color theorem!