Graph Explorer: Shortest Path & Coloring

Mode

Graph

Nodes 16

Extra edge density 0.35

Algorithm speed 3 steps/s

Nodes / edges

–

Status

idle

Path distance

–

Path edges

–

How it works

Shortest path (Dijkstra). Each node keeps a tentative distance from the green start node, initially infinite except the start (zero). The algorithm repeatedly "settles" the unvisited node with the smallest tentative distance (turns it blue), then relaxes its neighbours: if reaching a neighbour through the settled node is shorter than what it currently knows, the neighbour's distance is updated and it joins the yellow frontier. This continues until the red end node is settled, at which point walking the recorded predecessors backward reveals the shortest path, highlighted in teal.

dist[start] = 0; dist[v] = ∞ for v ≠ start
while unsettled nodes remain:
  u = unsettled node with min dist[u]
  settle u
  for each edge (u,v,w): dist[v] = min(dist[v], dist[u] + w)

Graph coloring (greedy / Welsh–Powell). Nodes are sorted by degree (busiest first) and colored one at a time, each getting the lowest-numbered color not already used by any of its already-colored neighbours. No optimal coloring is guaranteed, but this simple greedy rule typically stays close to the graph's true chromatic number — the minimum colors needed so no two connected nodes ever share one, the same constraint behind exam-timetable and radio-frequency assignment problems.

Nodes — how many vertices the random graph contains.
Extra edge density — beyond the spanning backbone that keeps the graph connected, how many additional random edges get added (denser graphs need more colors and have more competing shortest paths).
Algorithm speed — how many algorithm steps play per second, so you can watch the frontier expand or the colors get assigned one decision at a time.

Start End Frontier Settled Path

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.

Graph Explorer: Shortest Path & Graph Coloring