Graf () je množica vozlišč (), ki so med seboj povezana s povezavami (). Matematični zapis za graf je . Povezave so lahko usmerjene ali neusmerjene.

Slika 2: Graf

Usmerjen graf je tisti graf, ki ima vse povezave usmerjene. In posledica je, da se lahko iz ene točke premaknemo v drugo le v smeri povezave, nazaj pa po isti poti ne gre, razen če je le ta dvosmerna.

Slika 3: Usmerjen graf

Utežen graf je tisti graf, ki ima na vseh povezavah neko težo (npr. ceno, razdaljo). Ta nam pove koliko enot porabimo, da pridemo iz ene točke v drugo.

Slika 4: Utežen graf

Najkrajša pot na grafu je tista, ki iz ene točke pride v drugo tako, da je vsota vseh uteži na izbranih povezavah najmanjša.

Slika 5: Najkrajša pot iz vozlišča A v B.

Primer: Zanima nas katera pot je od A do C najkrajša. Najprej pogledamo vse možnosti. Možne izbire so ABC, AC, ADC in AEDC. Sedaj pogledamo vrednosti uteži. ABC: 1 + 3 = 4 AC: 8 ADC: 7 + 2 = 9 AEDC: 2 + 1 + 2 = 5 Med vsemi možnostmi izberemo ABC, saj ima ta najmanjši seštevek uteži (4).

OPOMBA: Da je pot najkrajša, ne pomeni, da vsebuje najmanj povezav, ampak da je vsota uteži na povezavah najmanjša.

Iskanju najkrajših poti rečemo kar problem najkrajših poti. Tu iščemo najbolj optimalno vrednost.

Poznamo pa seveda več različic tega problema:

• Najkrajše poti iz enega vozlišča
• Najkrajše poti do danega vozlišča
• Najkrajša pot med parom vozlišč
• Najkrajša pot med vsemi možnimi pari vozlišč

Za reševanje najkrajših poti poznamo tri algoritme:

• Dijkstrov algoritem (Iskanje najkrajše poti od nekega vozlišča le za nenegativne uteži.)
• Bellman-Fordov algoritem (Iskanje najkrajše poti od nekega vozlišča tudi za negativne uteži.)
• Floyd-Warshallov algoritem (Iskanje najkrajših poti med vsemi pari vozlišč s poljubnimi utežmi.)

Dijkstrov algoritem najde najkrajše poti iz izbrane točke do vseh ostalih točk. Med izvajanjem postopka gradimo drevo najkrajših poti.

Drevo najkrajših poti je vpeto drevo, ki vsebuje vse najkrajše poti iz izbranega vozlišča do vseh ostalih.

Slika 6: Primer za drevo najkrajših poti.

Ugotovitev: Če gledamo drevo najkrajših poti za vozlišče α ne bomo dobili prave najkrajše poti od vozlišča β do γ. V primeru, da bo rešitev prava pa bo to zgolj naključje oz. vsako vozlišče ima svoje drevo najkrajših poti.

Uporaba:

• Iskanje najkrajše poti iz enega kraja v drugega (utež: število kilometrov)
• Iskanje najhitrejše poti iz enega kraja v drugega (utež: čas)
• Iskanje najkrajše poti v omrežjih (začetno in končno vozlišče sta enaka, želimo pa da najhitreje pridemo čez vsa vozlišča).

Legenda oznak na grafih

Algoritem zgradi drevo tako, da vsakič doda iz množice vozlišč, ki še niso v drevesu vozlišče, ki ima najkrajšo pot od začetnega vozlišča.

DELOVANJE ALGORITMA:

Podano imamo:

• množico izbranih vozlišč (modra vozlišča)
• množico kandidatk za izbrano vozlišče (rdeča vozlišča)
• množico prostih vozlišč (oranžna vozlišča)
• začetno vozlišče

Postopek:

• začetno vozlišče damo v množico
• začetnemu vozlišču poiščemo kandidate za povezave in vozlišča do katerih vodijo, ter jih dodamo v množico in izbrišemo iz množice
• vsem vozliščem iz množice izračunamo najkrajšo pot od začetnega vozlišča
• med vsemi vozlišči iz izberemo tistega, ki ima najkrajšo pot (najmanjšo vrednost)

• dokler nista množici in prazni izvajaj:

  • poiščemo nove kandidate za povezave in vozlišča in jih dodamo v množico in izbrišemo iz množice

    • če najdemo neko kandidatko za izbrano povezavo, ki vodi do vozlišča,ki je že v potem:

      • če je vrednost najkrajše poti večja kot prejšnja potem

        • pustimo prejšnjo vrednost

      • če pa je vrednost najkrajše poti manjša kot prejšnja potem

        • spremenimo na novo vrednost
  • izberemo iz množice vozlišče z najmanjšo vrednostjo najkrajše povezave od začetnega vozlišča in ga damo v množico in izbrišemo iz množice .
• algoritem nam vrne drevo najkrajših poti

Iskali bomo najkrajše poti iz točke A do preostalih.

Slika 7: Začetno vozlišče in kandidatki za novo povezavo.

Slika 8: Izbira vozlišča C in novi možni povezavi.

Slika 9: Izbira vozlišča B in kandidatki za povezavo.

Slika 10: Konec algoritma -> drevo najkrajših poti

Rešili bomo nekoliko težji primer z devetimi vozlišči. Iskali bomo najkrajše poti iz točke A do preostalih.

Prikaz rešitve:

Slika 11: Problem in rešitev problema.

Spodaj si lahko v filmčku ogledate potek reševanja po korakih.

Katera od spodnjih slik predstavlja drevo najkrajših poti vozlišča za graf ?

Slika 12: Graf G

• Zapiski iz predavanj iz predmeta Optimizacija, študijsko leto 2010/2011
• Jernej Kozak, Podatkovne strukture in algoritmi, DMFA, ljubljana 1986
• Dijkstra's Shortest Path Algorithm
• Primoz Umek, PSIA-seminarska naloga, Dijkstrov algoritem.pdf
• Bojan Možina, Najkrajše poti in algoritem Bellman-Ford
• DIJKSTRA ALGORITHM
• Wikipedija - Dijkstrov algoritem
• Dijkstra R2Wiki
• MY liTTleBloG