Python - Najbliži gradovi (Dijkstrin algoritam)


U ovom primjeru se demosntrira upotreba matrica u rješavanju grafovskih problema. Graf G(v,e) je skup čvorova v (vertex, node) povezanih lukovima e (edge). Osim oznaka, lukovi grafa mogu imati i različita kvantitativna obilježja, koja predstavljaju npr. cijenu, dužinu puta i sl. Pretraživanjem je moguće pronaći najkraći put između dva čvora grafa, npr. između čvorova 1 i 2 grafa na sljedećoj slici:



Ako čvorovi grafa predstavljaju naselja, a lukovi direktne puteve između njih, najkraći put u grafu odgovara najkraćem putu između dva naselja (lokacije), koji se npr. može dobiti pomoću aplikacije www.google.com/maps. Grafovi se mogu predstaviti matricama sisusedstva i matricama incidencije, u koje se smještaju neophodne informacije iz grafa, kao što je npr. sljedeći graf:



Matrica susjedstva (adjacency) A = [aij] pokazuje da li su dva čvora povezana lukom. Indeksi i i j su indeksi čvorova, a elementi matrice aij mogu da označavaju npr. da li su dva čvora povezana (0 ili 1), broj lukova ili dužinu luka ij




Matrica incidencije B = [bij] pokazuje da li je neki čvor povezan (incidentan) s nekim lukom. Indeks i je čvor, j je oznaka luka, a element matrice bij = 0 ili 1 označava da li je čvor i povezan s lukom j




Jedan od najpoznatijih algoritama za pronalaženje najkraćeg puta između dva čvora u grafu je Dijkstrin algoritam. Osnovna verzija Dijstrinog algoritma predstavlja varijantu pretraživanja u širinu (breadth-first-search), jer posjećuje susjedne čvorove po redosljedu njihovog pronalaženja. Za pamćenje njihovog redosljeda koristi se struktura reda čekanja (queue), u koju se novi elementi dodaju na kraj reda, a uzimaju s početka reda. Prilikom pretraživanja, poseta svakom čvoru se označava, kako bi se kasnije posećenost mogla provjeriti i pretraživanje nastavilo obilaskom ostalih povezanih, još neposjećenih čvorova.

Osnovna verzija Dijkstrinog algoritma ne pretpostavlja jednake težine/dužine lukova i čvorove označava dužinom najkraćeg puta (od početnog čvora) i pronalazi najkraće puteve od početnog čvora do svih ostalih čvorova grafa. Unapređena verzija algoritma koristi strukturu prioritetnog reda čekanja umesto običnog, radi značajnog unapređenja performansi. Program za osnovnu verziju Dijkstrinog algoritma u jeziku Python se može napisati kao u nastavku:

""" Program pronalazi najkraći put između dva čvora
    u zadanom grafu.

    U ovom školskom primjru graf je definisan unaprijed
    unesenom matricom dužina lukova (adjacency matrix).
    Za pronalaženje najkraćeg puta koristi se
    Dijkstrin algoritam.
"""
INF = float('inf')

def dijkstra(graf,od):
#
#   Dijkstrin algoritam koji pronalazi najkraće puteve
#   u grafu od zadanog čvora do svih ostalih
#
    cvorovi = [i for i in range(len(graf))]
    poseceni = [od]
    put = {od:{od:[]}}
    cvorovi.remove(od)
    rastojanja_cvorova = {od:0}
    preth = sled = od

    while cvorovi:
        rastojanja = INF
        for v in poseceni:
            for d in cvorovi:
                novo_rastojanje = graf[od][v]+graf[v][d]
                if novo_rastojanje < rastojanja:
                    rastojanja = novo_rastojanje
                    sled = d
                    preth = v
                    graf[od][d] = novo_rastojanje

        put[od][sled] = [i for i in put[od][preth]]
        put[od][sled].append(sled)

        rastojanja_cvorova[sled] = rastojanja

        poseceni.append(sled)
        cvorovi.remove(sled)
    return rastojanja_cvorova, put

# Testni primer grafa
graf = [[0,3,4,INF,INF],
        [3,0,INF,2,INF],
        [4,INF,0,7,2.5],
        [INF,2,7,0,1],
        [INF,INF,2.5,1,0]]

print("Program pronalazi najkraći put između dva čvora")
print("u grafu koji je definisan matricom dužina lukova")
print("(adjacency matrix):")
print(" (0) ┌ ┐")
print(" 4 / \ 3 │ 0 3 4 - - │")
print(" / \ │ 3 0 - 2 - │")
print(" (2) (1) │ 4 - 0 7 2.5 │")
print(" | \ 7 / │ - 2 7 0 1 │")
print(" 2.5 | \ / 2 │ - - 2.5 1 0 │")
print(" (4)--(3) └ ┘")
print(" 1 ")

# Najkraći put između dva zadana čvora
od = int(input("Unesi početni čvor putanje (0..4): "))
do = int(input("Unesi krajnji čvor putanje (0..4): "))

# Pronalaženje najkraćih puteva do svih ostalih čvorova
rastojanja, put = dijkstra(graf,od)

print("\nNajkraći put između čvorova",od,"i", do, "dužine",rastojanja[do], "je:\n", put[od][do])

Izvršavanje programa za pronalaženje najkraćeg puta između čvorova 2 i 1 testnog primjera grafa daje sljedeći rezultat:

Program pronalazi najkraći put između dva čvora
u grafu koji je definisan matricom dužina lukova
(adjacency matrix):

(0) ┌ ┐
4 / \ 30 3 4 - - │
/ \ │ 3 0 - 2 - │
(2) (1) │ 4 - 0 7 2.5 │
| \ 7 / │ - 2 7 0 12.5 | \ / 2 │ - - 2.5 1 0 │
(4)--(3) └ ┘
1

Unesi početni čvor putanje (0..4): 2
Unesi krajnji čvor putanje (0..4): 1
Najkraći put između čvorova 2 i 1 dužine 5.5 je:
[4, 3, 1]