Trace graph algorithms step by step
Use this graph algorithm visualizer to compare the methods taught in an Intro to Algorithms or data structures course. Start with the loaded weighted graph and its Dijkstra result, then inspect the working one action at a time. The diagram shows your vertices and weighted edges, while the tables preserve the state after each action. The goal is to explain why a result follows from a graph, so you can compare your own homework trace with the same inputs and tie-breaking rules.
Enter the graph from your assignment
List all vertex names, including vertices with no incident edges. Separate names with spaces or commas. Enter each edge on a separate line using three fields: the starting vertex, ending vertex and integer weight. In directed mode, an edge goes only from the first vertex to the second. In undirected mode, a single line supplies both directions. Do not repeat the reverse line in undirected mode. Self-loops are accepted, but parallel edges between the same ordered pair are not.
The editor supports up to 16 vertices and 80 edges, with integer weights between −1000000 and 1000000. Names begin with a letter and contain up to eight letters, digits or underscores. These limits keep traces manageable on a phone. Invalid entries clear the diagram and answer until corrected; they never silently disappear from a partially parsed graph. Changing the graph, source or algorithm returns the view to the complete result.
Choose the right algorithm
BFS uses a first-in, first-out queue and measures distance by the number of edges. It ignores weights, even when those weights appear on the drawing. DFS follows a branch before returning to try another neighbor. Its stack displays the active recursive calls, with the top on the right. DFS reports discovery and finish times across the whole forest, visiting the source first and then any unvisited vertices. Its depth column describes the DFS tree, not a shortest path.
Dijkstra finds shortest weighted distances when all edge weights are nonnegative. The priority queue shows unsettled vertices in increasing distance order. Bellman-Ford supports negative edge weights by repeatedly scanning and relaxing edges. It also checks for a negative cycle reachable from the source. Affected vertices and all their downstream vertices receive −∞ because no finite shortest distance exists. An unreachable negative cycle does not invalidate distances from this source.
Prim and Kruskal answer a different question: which undirected edges connect each component with minimum total weight? Their result is a minimum spanning tree for a connected graph or a minimum spanning forest otherwise. Prim grows a tree using connection keys; those keys are individual edge weights, not source-to-vertex distances. Kruskal considers edges in weight order and uses disjoint sets to reject cycles. Topological sort uses a queue of zero-indegree vertices in a directed graph. If a cycle prevents completion, the partial removal sequence is not presented as a valid ordering.
Worked weighted-path example
The loaded example uses vertices s, t, x, y and z, with source s. Running the library gives Dijkstra distances s = 0, t = 8, x = 9, y = 5 and z = 7. The shortest route to x goes through y and t: s → y contributes 5, y → t contributes 3 and t → x contributes 1, for a total of 9. The direct s → t edge costs 10, so discovering an edge does not mean its endpoint already has its final distance.
The extraction order is s, y, z, t, x. Bellman-Ford gives the same distances on this graph. Switching to BFS instead gives t = 1, y = 1, x = 2 and z = 2 because BFS counts edges rather than adding weights. Switching to DFS gives discovery order s, t, x, z, y; s is discovered at time 1 and finishes at time 10. All these results come from the same graph, but they answer different questions.
Read the trace and check your reasoning
Choose First step to inspect initialization, then Next to move forward. Previous revisits a state; Final step restores the completed state. You can also select any numbered row in the step table. The frontier and vertex values in that row are snapshots after the stated action. Infinity means a vertex is unreachable for shortest-path searches. Parents show predecessor links. Thick edges on the diagram show those links or the accepted spanning-forest edges, depending on the algorithm.
Load the MST example to compare Prim and Kruskal: both produce total weight 37 with eight accepted edges, although their selected trees can differ because equal-weight alternatives exist. Vertex and neighbor ties follow the vertex list; Kruskal breaks equal-weight edge ties by input order. The priority queue is displayed as a sorted conceptual queue, not a binary-heap animation. Use the Algorithms Lab for related exercises and the hash table simulator to study another core data structure. Your course may choose a different neighbor order, so compare distances and invariants before treating a different traversal sequence as an error.