Witam
Mam podane pnukty na płaszczyźnie i musze podać najmniejszą odległość między dwoma punktami. Naiwnie można to zrobić w O(n^2) ale ponoć da się to machnąć w O(n log(n)). Czy ktoś ma pomysł jak to ugryźć?
Pozdrawiam.
0
0
http://pl.wikipedia.org/wiki/Algorytm_Dijkstry
szukanie najkrótszej drogi w grafie. Zazwyczaj wykorzystywany przy problemie komiwojażera (szukanie cykli), ale można go wykorzystać też do szukania dowolnej "najkrótszej drogi"
0
Koziołek ale jak do tego problemu mogę zastosować algorytm Dijskstry ? Przecież między tymi punktami nie ma żadnych ustalonych połączeń. A ja musze jedynie odnaleźć najmniejszą odległośc między dwoma punktami (odległość w sensie geometrii analitycznej).
0
Dzięki wielkie - o to chodziło.