Computer science · Algorithms

Weighted graph algorithms laboratory

One graph, three different questions: what is the shortest path? How can all nodes be connected with the lowest total weight?

Read the article on the three algorithms

Dijkstra repeatedly settles the unvisited node with the smallest tentative distance. It requires non-negative weights; here all weights are 1 to 20.

Graph ready. Press Play or Next step.

Step0 / 0

Selected edges0

Distance to target—

Rejected edges0

Unused edge Selected edge Examined edge Path to target

What are you seeing?

Dijkstra solves a path problem. Prim and Kruskal solve the minimum spanning tree problem: their chosen edges may differ, but the minimum total weight agrees. The layout uses geometric positions; edge weights are random and do not represent screen distances.