Witam. Mam problem ze znalezieniem najkrótszej drogi w grafie.
Graf wygląda tak:
- mamy |V|=10 wierzchołków
- |E|<20 - ilość krawędzi
- graf jest nieskierowany
- musi być spójny
- nie zawiera pętli
Zadanie zakłada wygenerowanie takiego grafu i zrobienie paru rzeczy. Problem pojawia się przy znajdowaniu najkrótszej drogi z wierzchołka a do b.
np. mamy taki graf (w przykładzie podam jakiś mniejszy, bo 10 w. i ok 15 k. to trochę dużo)
1 2 3 4 5
1[x 0 0 1 0]
2[0 x 0 1 1]
3[0 0 x 0 1]
4[1 1 0 x 1]
5[0 1 1 1 x]
Jedynki reprezentują połączenie (krawędź) pomiędzy wierzchołkami, zera ich brak, a x-y to chyba oczywiste - graf ma nie zawierać pętli.
Dla jasności mamy takie połączenie wierzchołków:
1-4
2-4
2-5
3-5
4-1
4-2
4-5
5-2
5-3
5-4
Czyli graf wygląda tak:
I załóżmy, chcę znaleźć najkrótszą scieżkę z wierzchołka 1 do 3.
Mam tylko daną taką tablicę jak powyżej. Krawędzie są bez wag, także nie mogę zastosować klasycznego algorytmu Dijkstry, ani od niego pochodnych. Przynajmniej żaden z tych, które znam.
Proszę o pomoc w implementacji. Bo właściwie potrzebuję to na wczoraj!:P