Algoritmus pro hledání nejkratších cest může znít jako problém určený hlavně pro navigace. Ve skutečnosti jde o jednu ze základních úloh teoretické informatiky. Stejné principy se používají při práci s počítačovými sítěmi, dopravou nebo jinými systémy, které lze popsat pomocí grafů.

Jednou z klasických úloh je All-Pairs Shortest Paths, zkráceně APSP. Cílem je určit vzdálenost mezi každou dvojicí vrcholů v grafu. Pro velké a husté sítě však přesný výpočet rychle začne být velmi náročný.

Proto se používají aproximační algoritmy. Nemusí vrátit dokonale přesné číslo, ale garantují, že chyba nepřekročí předem stanovenou hranici.

Řešení z roku 1996 mělo jedno slabé místo

Dorit Dor, Shay Halperin a Uri Zwick představili už na konferenci FOCS v roce 1996 práci All Pairs Almost Shortest Paths. Z jejich výsledků vychází algoritmus, který dokáže u vybraných dvojic vrcholů garantovat takzvanou 2-aproximaci.

To znamená, že vypočtená vzdálenost není větší než dvojnásobek skutečné nejkratší cesty. Pokud je skutečná vzdálenost například deset hran, výsledek nepřesáhne dvacet. Problém nastával u vrcholů, které leží relativně blízko sebe. Původní přístup dokázal při dané časové složitosti nabídnout tuto garanci pro dvojice vzdálené alespoň k hran.

Manoj Gupta z Indian Institute of Technology Gandhinagar nyní ukázal, že tuto hranici lze výrazně snížit. Jeho práce Improved 2-Approximate Shortest Paths for close vertex pairs byla přijata na 66. ročník IEEE Symposium on Foundations of Computer Science, tedy FOCS 2025.

Místo k stačí O(log k)

Guptův randomizovaný kombinatorický algoritmus používá vnořené vzorkování vrcholů v několika úrovních. Díky tomu dokáže získat vhodné orientační body i pro podstatně kratší cesty.

Zásadní je především matematický výsledek. Zatímco předchozí přístup poskytoval při časové složitosti přibližně Õ(n^(2+O(1/k))) dvojnásobnou aproximaci pro dvojice vzdálené alespoň k, Gupta dosahuje přibližně Õ(n^(2+1/k)) a garanci rozšiřuje už na dvojice vzdálené O(log k).

Zajímavý je případ, kdy k odpovídá log n. Algoritmus se potom dostává na téměř kvadratickou složitost Õ(n²) a 2-aproximaci poskytuje pro dvojice vzdálené už O(log log n).

Neznamená to, že by nyní počítače dokázaly okamžitě a přesně spočítat všechny nejkratší cesty v libovolně velké síti. Gupta sám popisuje svůj výsledek jako první zlepšení této konkrétní hranice za více než 25 let. Algoritmus je navíc randomizovaný a správnou aproximaci garantuje s vysokou pravděpodobností.