La ricerca del cammino minimo nei grafi di grandi dimensioni e debolmente connessi

La ricerca ricorrente dei cammini minimi fra due vertici, in un grafo di grandi dimensioni e debolmente connesso,implica tempi lunghissimi di esecuzione o,in alternativa,un esorbitante impegno di memoria,se tutti i possibili çammini sono preventivamente calcolati e utilizzati di volta in volta. Il procedimento di calcolo,di cui si tratta,rende possibile una sensibile economia di tempo, o di memoria ,rispettivamente, nell'uno o nell'altro caso. Esso presuppone il preventivo riconoscimento nel grafo di parti 'debolmente 'connesse fra loro (per es. grafi rappresentativi di aeroporti, di reti ferroviarie internazionali, ecc.) e la loro suddivisione in sottografi. Il procedimento prevede una ridistribuzione dei vertici e degli spigoli in modo tale che i "sottografi" acquisiscano la proprietà che i cammini minimi fra i vertici di ognuno siano minimi in assoluto,cioè coincidano con i cammini minimi calcolati nell'intero grafo. Il calcolo dei cammini minimi fra due vertici qualsiasi risulta più rapido per le proprietà che conseguono dalla suddivisione del grafo nei "sottografi" sopra specificati.