Graph Algorithms
Graphs are used to represent roads, computer networks, connections and task dependencies. Enter a few connections, such as A-B:4, and the page will draw the graph. Choose an algorithm and follow how it works, step by step. You can explore graph traversal, shortest paths, minimum spanning trees and topological ordering. The visualizer also shows the data structure used by each algorithm, such as a queue, stack, priority queue or table. Every important decision comes with a simple explanation.
Interactive workspace
Finds the shortest distance from a starting node. It always selects the closest unfinished node next. It works with edge weights of 0 or more.
A-B:4 means an undirected connection between A and B with weight 4. A>B:4 means a directed connection from A to B with weight 4. The weight is optional. Use letters A to H and up to 14 edges.
Examples
The graph
Step 0 of 17
- current
- waiting
- finished
- in the result
Edges relaxed or checked
0
Finalised order
0
of 6 nodes
Nodes
6
Edges
9
Working data
Not used by this step.
Finalised order
Nothing yet.
Step-by-step explanation
0 of 17 steps
Press Next or Play to follow each decision made by the algorithm.
About Dijkstra
- Time
- O(V² ) as written, O((V + E) log V) with a heap
- Space
- O(V)
- Works on
- Weights of 0 or more
Under the hood
From input to screen
The experiment follows this process. Select any box to see what it does and which function or component is behind it.
Pipeline: input, parsing, simulation, steps, visualization
Click any box to see what it does and why it is built that way.
Start
Input
- What it does
- You enter graph connections such as A-B:4 or A>B:2, choose one of eight algorithms and select a starting node when needed.
- Where it lives
- GraphDemo.tsx (text, algo, source)
- Why it is built this way
- The graph is created from your input each time. This keeps the displayed graph and the algorithm's calculations in sync.
Technical notes
How Graph Algorithms works
How the algorithm works
The simulator converts your input into a graph with up to 8 nodes and 14 edges. A dash (-) creates an undirected connection. An arrow (>) creates a directed connection. A weight can be added to a connection. The selected algorithm processes the graph and records every important decision. Each step contains the state of the nodes and edges, the queue, stack or table being used and a simple explanation.
Some algorithms also have specific requirements. Prim's and Kruskal's need an undirected graph. Topological Sort needs a directed graph. Dijkstra needs edge weights of 0 or more. If the graph does not meet these requirements, the page explains the problem instead of showing an incorrect result.
Important steps
- 01Read and validate the connections. Node names must be between A and H, and weights must be between −20 and 99.
- 02Check whether the graph is suitable for the selected algorithm.
- 03Run the algorithm and record every decision.
- 04Show the result, such as traversal order, shortest distances, a minimum spanning tree or topological order.
- 05Use Back, Next and Play to move through the recorded steps.
Relevant variables
- V, E
- Number of nodes and edges.
- queue, stack
- Data structures used by BFS and DFS to decide which node to visit next.
- dist[]
- Best known distance from the starting node to each other node.
- priority queue
- Dijkstra's list of nodes, ordered by the smallest known distance.
- groups
- Tracks which connected group each node belongs to. Used by Kruskal's Union-Find approach.
- in-degree
- Number of incoming edges for a node. Used by Topological Sort.
Time and space complexity
| Algorithm | Time | Space |
|---|---|---|
| BFS, DFS, Topological Sort | O(V + E) | O(V) |
| Dijkstra (as implemented) | O(V²), O((V + E) log V) with a heap | O(V) |
| Bellman-Ford | O(V·E) | O(V) |
| Floyd-Warshall | O(V³) | O(V²) |
| Prim's (as implemented) | O(V·E), O(E log V) with a heap | O(V) |
| Kruskal's | O(E log E) | O(V) |
V is the number of nodes and E is the number of edges. Dijkstra and Prim's use a simple scan in this implementation. A heap-based approach can make them more efficient for larger graphs.
Example input and output
Input
- Edges: A-B:4 A-C:2 B-C:1 B-D:5 C-D:8 C-E:10 D-E:2 D-F:6 E-F:3
- Algorithm: Dijkstra from A
Output
- Distances: A = 0, B = 3, C = 2, D = 8, E = 10, F = 13.
- Prim's and Kruskal's both produce a minimum spanning tree with a total weight of 13.
Edge cases
- Disconnected graph: BFS and DFS show which nodes cannot be reached. Prim's stops after processing the connected group containing the starting node.
- Negative cycle: Bellman-Ford and Floyd-Warshall report a negative cycle instead of returning an incorrect shortest distance.
- Directed cycle: Topological Sort reports that a valid ordering is not possible.
- Undirected negative edge: It is treated as a negative cycle because the edge can be followed in both directions repeatedly.
- Invalid graph: Self-loops, repeated edges, weights outside the allowed range, more than 8 nodes or more than 14 edges are rejected with a clear message.
Where the code lives
- Enginesrc/lib/graph.ts
- Workspacesrc/components/GraphDemo.tsx
- Checkstests/graph.test.ts