Na adrese https://coding-challenge.websupport.sk pripravil Websupport vrámci pracovného náboru pár IT úloh. Zaujala ma posledná 4tá úloha, ktorá sa týka riešenia grafu:
Nachádzate sa na recepcii (to je ten krúžok odlišnej farby s označením X). Snažíte sa vcítiť do zmýšľania developerov… Určite sa budú schovávať čo najďalej od recepcie. Keďže sú pohodlní a nechce sa im chodiť zbytočne ďaleko, vybrali si najkratšiu možnú cestu. Tak čo? Uhádneš v ktorej miestnosti sa skryli?
Graf má uzly / vrcholy ( nodes / Vertices ) , ktoré predstavujú napr. mestá.
Ďalej má hrany ( Edges ), ktoré predstavujú spojnice, zvyčajne cesty.
Keď majú hrany svoje hodnoty (dĺžka cesty), ide o vážený graf.
Algoritmy pre najkratšiu cestu:
- Dijkstra - zložitosť E * log(V) - najrýchlejší, len kladné hodnoty hrán
- Bellman-Ford - zložitosť E * V
- Floyd-Warshall - zložitosť V³ - ráta naraz všetky vzdialenosti, najpomalší
Floyd - Warshall
Moja prvá otázka, keď som pozrel na obr grafu bola, v akej forme ho zapísať. V tomto algoritme je to dvojrozmerné pole (matica), kde súradnice v poli určujú zdrojový a cieľový uzol (mesto), a hodnota zapísaná na danej pozícií zas hodnotu hrany (dĺžka cesty). Ak hrana medzi uzlami neexistuje, nastavíme MAX, ak ukazuje sám na seba nastavíme 0 (uhlopriečka).
/* floyd.c
*
* Najkratsia cesta podla algoritmu Floyd-Warshall
*
* Vytvorene: 2015-04-16
* Web autora: https://github.com/sysilion/ShortestPath/blob/master/src/main.c
*
* okrem najkratsej vzdialenosti z pociatocneho uzla ku vsetkym ostatnym,
* vypise aj uzly cez ktore sa tam po najkratsej ceste dostal
*/
#include <stdio.h>
#define UZLOV 14 // POCET UZLOV, RATAME AJ S 0, TEDA UZLY 0-13 = 14
#define MAX 999 // KONSTANTA OMNOHO VACSIA AKO BEZNA CESTA, PRE NEPREPOJENE UZLY
void PrintPath(int path[][UZLOV], int src, int des){ // VYPISE UZLY PO CESTE PRE NAJKRATSIU CESTU
if(path[src][des] != 0){
PrintPath(path, src, path[src][des]); // REKURZIA PRE ZACIATOK - MEDZIUZOL
printf(" v%d ->", path[src][des]); // VYPISE JEDEN MEDZIUZOL V CESTE
PrintPath(path, path[src][des], des); // REKURZIA PRE MEDZIUZOL - KONIEC
}
}
int main(){
int start;
int i, j, k;
// ZADANY GRAF STYLOM 2D POLA ZDROJ-CIEL VZDIALENOSTI MEDZI UZLAMI (LEN PRIAME)
// SAM NA SEBA UZOL VZDIALENOST 0
// AK NIE JE PRIAMY PREPOJ (HRANA), JE MAX
int data[UZLOV][UZLOV] = {
{0, MAX, MAX, MAX, MAX, 2, MAX, MAX, 3, MAX, 4, MAX, MAX, MAX},
{MAX, 0, MAX, 1, MAX, 8, MAX, 3, MAX, MAX, MAX, MAX, MAX, MAX},
{MAX, MAX, 0, MAX, MAX, 3, MAX, MAX, MAX, 8, 2, MAX, 2, MAX},
{MAX, 1, MAX, 0, 2, MAX, 5, MAX, 7, MAX, MAX, MAX, MAX, 2},
{MAX, MAX, MAX, 2, 0, 6, MAX, MAX, MAX, MAX, MAX, MAX, 2, 3},
{2, 8, 3, MAX, 6, 0, 2, MAX, MAX, MAX, 1, MAX, MAX, MAX},
{MAX, MAX, MAX, 5, MAX, 2, 0, MAX, 3, MAX, MAX, MAX, MAX, MAX},
{MAX, 3, MAX, MAX, MAX, MAX, MAX, 0, MAX, MAX, MAX, 2, MAX, 1},
{3, MAX, MAX, 7, MAX, MAX, 3, MAX, 0, MAX, MAX, MAX, MAX, MAX},
{MAX, MAX, 8, MAX, MAX, MAX, MAX, MAX, MAX, 0, MAX, 2, 4, MAX},
{4, MAX, 2, MAX, MAX, 1, MAX, MAX, MAX, MAX, 0, MAX, 2, MAX},
{MAX, MAX, MAX, MAX, MAX, MAX, MAX, 2, MAX, 2, MAX, 0, 5, 2},
{MAX, MAX, 2, MAX, 2, MAX, MAX, MAX, MAX, 4, 2, 5, 0, MAX},
{MAX, MAX, MAX, 2, 3, MAX, MAX, 1, MAX, MAX, MAX, 2, MAX, 0}
};
int path[UZLOV][UZLOV] = {}; // cesta medzi 2 uzlami cez treti
printf("Pociatocny uzol (0~%d) : ", UZLOV-1);
scanf("%d", &start);
// pocitame vzdialenost medzi i-j, cez uzol k
// ak je vzdialenost cez k kratsia ako priama resp doterajsia najkratsia (data), aktualizujeme
for(k = 0; k < UZLOV; k++){
for(i = 0; i < UZLOV; i++){
for(j = 0; j < UZLOV; j++){
if (data[i][j] > data[i][k] + data[k][j]){
data[i][j] = data[i][k] + data[k][j];
path[i][j] = k; // LEN PRE VYPIS CESTY
}
}
}
}
for(i = 0; i < UZLOV ; i++){ // VYPIS PRE KAZDY CIELOVY UZOL
if(start == i) continue; // POCIATOCNY BOD IGNORUJ
else if(data[start][i] != MAX){ // IBA AK JE NAJDENA CESTA
printf("U%d\t%d", i, data[start][i]);
printf("\t ( u%d ->", start);
PrintPath(path, start, i); // VYPISE UZLY KADE VEDIE CESTA
printf(" u%d )\n", i);
}
}
return 0;
}
Po skompilovaní a spustení vidím vo výpise aj ktorými uzlami je cesta najkratšia:
$ ./floyd
Pociatocny uzol (0~13) : 0
U1 10 ( u0 -> u5 -> u1 )
U2 5 ( u0 -> u5 -> u2 )
U3 9 ( u0 -> u5 -> u6 -> u3 )
U4 7 ( u0 -> u5 -> u10 -> u12 -> u4 )
U5 2 ( u0 -> u5 )
U6 4 ( u0 -> u5 -> u6 )
U7 11 ( u0 -> u5 -> u10 -> u12 -> u4 -> u13 -> u7 )
U8 3 ( u0 -> u8 )
U9 9 ( u0 -> u5 -> u10 -> u12 -> u9 )
U10 3 ( u0 -> u5 -> u10 )
U11 10 ( u0 -> u5 -> u10 -> u12 -> u11 )
U12 5 ( u0 -> u5 -> u10 -> u12 )
U13 10 ( u0 -> u5 -> u10 -> u12 -> u4 -> u13 )Pre každé dva uzly vyskúša cestu cez tretí (každý) a ak je kratšia, nahradí dĺžku v matici novou najkratšou. Takto v podstate stačí jeden výpočet a následne z matice vieme vybrať najkratšie vzdialenosti medzi rôznymi dvoma uzlami.
Dôležité je aby bol cyklus určujúci tretí (prechodný) uzol ten vonkajší (k), aby bol odskúšaný na všetkých kombináciách.
Algoritmy pre najkratšiu cestu sú popísané aj tu:
https://www.itnetwork.sk/navrh/algoritmy/algoritmy-grafova/hladanie-najkratsia-cesta-v-grafe
Žiadne komentáre:
Zverejnenie komentára