Search algorithmsCTRL K
The cheapest road network for Paraná
· a minimum spanning tree over real cities and distances/signatures/parana-roadsbuilt on KruskalCITIES
25
real coordinatesCANDIDATE ROADS
46
3 nearest neighbours eachROADS BUILT
0/ 24
cities − 1 when doneTOTAL KM
0
of asphalt so farREJECTED
0
would only close a loopconsideringbuiltpath that already joins the endsrejected (dashed)connected city25 cities · 46 candidate roads · 94 steps
step 0 / 93
ROADS BY LENGTH46
1Ponta Grossa – Castro37 km·
2Cascavel – Toledo38 km·
3Londrina – Apucarana40 km·
4Francisco Beltrão – Pato Branco42 km·
5Campo Mourão – Cianorte48 km·
6Maringá – Apucarana50 km·
7Londrina – Cornélio Procópio55 km·
8Ponta Grossa – Irati64 km·
9Maringá – Paranavaí67 km·
10Paranavaí – Cianorte67 km·
11Cornélio Procópio – Jacarezinho69 km·
12Pato Branco – Palmas73 km·
13Maringá – Cianorte74 km·
14Umuarama – Cianorte74 km·
15Curitiba – Paranaguá77 km·
16Guarapuava – Pitanga77 km·
17Londrina – Maringá79 km·
18Telêmaco Borba – Castro80 km·
19Guarapuava – Irati81 km·
20Campo Mourão – Maringá83 km·
21Apucarana – Cornélio Procópio93 km·
22União da Vitória – Palmas94 km·
23Pato Branco – Laranjeiras do Sul95 km·
24Irati – União da Vitória95 km·
25Guarapuava – Laranjeiras do Sul96 km·
26Curitiba – Ponta Grossa97 km·
27Ponta Grossa – Telêmaco Borba97 km·
28Francisco Beltrão – Laranjeiras do Sul98 km·
29Laranjeiras do Sul – Pitanga98 km·
30Castro – Irati99 km·
31União da Vitória – Guarapuava100 km·
32Umuarama – Campo Mourão101 km·
33Campo Mourão – Pitanga101 km·
34Curitiba – Castro103 km·
35Paranavaí – Campo Mourão109 km·
36Toledo – Umuarama115 km·
37Francisco Beltrão – Palmas115 km·
38Cascavel – Laranjeiras do Sul116 km·
39Foz do Iguaçu – Toledo122 km·
40Telêmaco Borba – Apucarana122 km·
41Jacarezinho – Londrina124 km·
42Cascavel – Foz do Iguaçu129 km·
43Jacarezinho – Telêmaco Borba145 km·
44Foz do Iguaçu – Francisco Beltrão166 km·
45Paranaguá – Castro172 km·
46Paranaguá – Ponta Grossa173 km·
CURRENT STEP0 km
25 cities and 46 candidate roads, each city linked to its 3 nearest neighbours. Sort the roads by length: the shortest is Ponta Grossa – Castro (37 km).
The cheapest road network for Paraná
Connect every city with as little road as possible: that is a minimum spanning tree. Kruskal sorts all candidate roads by length and takes them shortest first, skipping any road whose two ends are already connected through roads taken earlier, because it would only add a loop.
Union-find answers 'already connected?' in near-constant time, so the sort dominates. The same computation lays out power grids, fibre backbones, water mains and the clustering step of single-linkage; here the distances are great-circle kilometres between real coordinates.
What to notice
A rejected road is the longest road of the loop it would close: the violet path already joins its two ends, and every piece of that path is shorter, even when the detour is hundreds of kilometres.
The tree minimises total asphalt, not driving distance: Foz do Iguaçu to Francisco Beltrão is a long way around, and that is the price of the cheapest network.
The tree has exactly cities − 1 roads, whatever the candidates were.