Legrövidebb út meghatározása gráfokban

Az előző bejegyzésben gráfok ábrázolásával és implementációjával foglalkoztunk. Most arra keressük a megoldást, hogy hogyan lehet meghatározni egy gráf egy adott csúcsából a többi csúcsba vezető legkisebb élsúlyösszegű, vagy más szóval legrövidebb utakat. Ez a kérdés számos, gyakorlatban felmerülő, gráffal modellezhető problémában felmerül. Például utazáskor a távolságban vagy időben legrövidebb út megtalálása, vagy számítógéphálózatokban a csomagtovábbítás optimalizálása.

A kérdésre a választ a Dijkstra algoritmussal adjuk meg. Az algoritmus Edsger W. Dijkstra holland informatikusról kapta a nevét, aki 1959-ben publikálta azt.

Az algoritmus elve röviden:

Sorra veszünk minden csúcsot, kezdve a megadott kezdőcsúccsal, és megvizsgáljuk az éppen aktuális csúcs még nem vizsgált szomszédait a kiinduló csúcstól vett távolság (össz élsúly) szempontjából. Ha egy szomszéd csúcs eddig ismert legrövidebb úthossza nagyobb, mint az aktuális csúcs eddig ismert legrövidebb úthossza + az aktuális csúcs és a szomszéd között levő út hossza, akkor a szomszéd csúcs eddig ismert legrövidebb úthosszát erre az összegre módosítjuk.

Ha ezt az aktuális csúcs minden eddig nem vizsgált szomszédjára elvégeztük, akkor az aktuális csúcsot vizsgáltnak (látogatottnak) minősítjük, és vesszük a következő vizsgálandó csúcsot. Egy olyan új aktuális, vizsgálni kívánt csúcsot választunk a még nem látogatott csúcsok közül, amely ezek közül a legrövidebb útvonallal rendelkezik, és újra elvégezzük az előbbi vizsgálatot és a szomszédos csúcsok legrövidebb távolságadatának szükség szerinti aktualizálását.

Mivel kezdetben a csúcsok addig ismert legrövidebb úthosszát nem ismerjük még, ezért ezt kezdőértékként minden csúcsra végtelenre állítjuk. A kiinduló csúcsra viszont e kezdőértéket 0-ra állítjuk, hiszen önmagától nulla távolságra van.

Ha már minden csúcsot megvizsgáltunk, azaz nincs már nem látogatottként nyilvántartott csúcs, akkor végeztünk, és ekkor az egyes csúcsok távolságadata lesz a kiinduló csúcstól vett legrövidebb távolság.

Ha azt is szeretnénk tudni, hogy a kiinduló csúcstól milyen útvonalon, azaz mely csúcsokon keresztül jutunk el a legrövidebb úton egy adott csúcsig, akkor a fenti lépesekben, amikor egy szomszéd csúcs eddig ismert legrövidebb úthosszát módosítjuk egy kisebb értékre, akkor egyúttal azt is el kell tárolni e csúcshoz, hogy melyik előző csúcstól jutottunk ide e rövidebb úttal. Ha ez minden csúcsra rendelkezésre áll, akkor a végén vissza tudjuk követni a legrövidebb útvonalat.

Ha ez a rövid összefoglaló nem lenne elegendő az algoritmus lényegének megértéséhez, akkor a „Dijkstra algoritmus” keresőkifejezést beírva a böngészőbe az interneten magyarul és angolul is számos részletesebb leírást találunk.

Az alább látható kódban az előző bejegyzésben megalkotott Graph osztályt egészítettük ki egy shortest_paths() nevű metódussal, amely a Dijkstra algoritmus alapján egy szótárban adja vissza a gráf megadott csúcsától minden más csúcshoz vezető legrövidebb úthosszakat és az odavezető utakat, azaz a csúcsok listáját. A megértést a fenti leírás tükrében a részletes kommentek segítik.


class Graph:
    # A korábbi bejegyzésben definiált metódusokat itt nem tüntettük fel.
    
    def shortest_paths(self, start_vertex_label: str):
        """Visszaadja egy szótárban a megadott csúcstól számított legrövidebb út hosszát, valamint az
        összes csúcshoz vezető legrövidebb útvonalat.
        """
        # Minden kiinduló ponttól számított, eddig ismert legrövidebb úthosszat minden csúcsra végtelenre
        # állítjuk, valamint az odavezető megelőző csúcsot None-ra, hiszen ezeket kezdetben nem ismerjük még.
        for vertex_label in self.vertices:
            self.set_vertex_data(vertex_label, [float('inf'), None])
            
        # A kiinduló csúcs eddig ismert legrövidebb úthosszát 0-ra állítjuk, hiszen önmagától nulla távra van.
        self.set_vertex_data(start_vertex_label, [0, None])

        # Minden csúcsot még nem vizsgáltnak (nem látogatottnak) állítjuk be.
        unvisited: dict = {label: vertex for label, vertex in self.vertices.items()}

        # Vesszük minden nem eddig még nem vizsgált csúcsot és aktulizáljuk a szomszédai legrövidebb
        # távolság adatát és az odavezető megelőző csúcsot is eltároljuk.
        while unvisited:
            # Egy olyan új aktuális vizsgálni kivánt csúcsot választunk a még nem látogatott csúcsok közül, amely
            # ezek közül a legrövidebb útvonallal rendelkezik.
            current = min(unvisited, key=lambda lbl: unvisited[lbl].data[0])

            # Az aktuális csúcsra kiszámítjuk a távolságot az összes nem látogatott szomszédjától.
            for neighbor, edge_distance_to_neighbor in self.neighbors[current]:
                if neighbor in unvisited:
                    neighbor_vertex_obj = self.vertices[neighbor]
                    # Ha a szomszéd csúcs eddig ismert legrövidebb úthossza nagyobb, mint a jelenlegi csúcs
                    # eddig ismert legrövidebb úthossza + a közöttük levő út hossza, akkor a szomszéd csúcs eddig
                    # ismert legrövidebb úthosszát erre az összegre módosítjuk.
                    if (distance := self.vertices[current].data[0] + float(edge_distance_to_neighbor)) < \
                            neighbor_vertex_obj.data[0]:
                        neighbor_vertex_obj.data = [distance, current]
            # Miután az aktuális csúcs minden szomszédját megvizsgáltuk és aktulizáltuk a szomszédai legrövidebb
            # távolság adatát és az odavezető megelőző csúcsot, az aktuális csúcsot megvizsgáltnak tekintjük és
            # kivesszük a még meg nem látogatottak listájából.
            unvisited.pop(current)

        # Segédfüggvény
        def shortest_path(end_vertex_label: str):
            """A start_vertex-től az argumentumként megadott végcsúcshoz vezető legrövidebb úton levő csúcsok
            listáját adja vissza a csúcsok adatai alapján.
            """
            path = []
            path.append(end_vertex_label)
            while previous_vertex := self.vertices[end_vertex_label].data[1]:
                path.append(previous_vertex)
                end_vertex_label = previous_vertex
            return path[-1::-1]
        
        # A visszatérési értékként szolgáló szótár előállítása, amelynek kulcsai a célcsúcsok címkéi, az
        # ezekhez tartozó értékek olyan tuple konténerek, amelyek első eleme a célcsúcsig vezető legrövidebb
        # út hossza, második eleme pedig a legrövidebb útat jelentő csúcsok listája.
        shortest_distances_and_paths = {vx_label: (self.vertices[vx_label].data[0], shortest_path(vx_label))
                                        for vx_label in self.vertices
                                        if self.vertices[vx_label].data[0] != float('inf')}

        return shortest_distances_and_paths

class Graph:

# A korábbi bejegyzésben definiált metódusokat itt nem tüntettük fel.

def shortest_paths(self, start_vertex_label: str):

"""Visszaadja egy szótárban a megadott csúcstól számított legrövidebb út hosszát, valamint az

összes csúcshoz vezető legrövidebb útvonalat.

"""

# Minden kiinduló ponttól számított, eddig ismert legrövidebb úthosszat minden csúcsra végtelenre

# állítjuk, valamint az odavezető megelőző csúcsot None-ra, hiszen ezeket kezdetben nem ismerjük még.

for vertex_label in self.vertices:

self.set_vertex_data(vertex_label, [float('inf'), None])

# A kiinduló csúcs eddig ismert legrövidebb úthosszát 0-ra állítjuk, hiszen önmagától nulla távra van.

self.set_vertex_data(start_vertex_label, [0, None])

# Minden csúcsot még nem vizsgáltnak (nem látogatottnak) állítjuk be.

unvisited: dict = {label: vertex for label, vertex in self.vertices.items()}

# Vesszük minden nem eddig még nem vizsgált csúcsot és aktulizáljuk a szomszédai legrövidebb

# távolság adatát és az odavezető megelőző csúcsot is eltároljuk.

while unvisited:

# Egy olyan új aktuális vizsgálni kivánt csúcsot választunk a még nem látogatott csúcsok közül, amely

# ezek közül a legrövidebb útvonallal rendelkezik.

current = min(unvisited, key=lambda lbl: unvisited[lbl].data[0])

# Az aktuális csúcsra kiszámítjuk a távolságot az összes nem látogatott szomszédjától.

for neighbor, edge_distance_to_neighbor in self.neighbors[current]:

if neighbor in unvisited:

neighbor_vertex_obj = self.vertices[neighbor]

# Ha a szomszéd csúcs eddig ismert legrövidebb úthossza nagyobb, mint a jelenlegi csúcs

# eddig ismert legrövidebb úthossza + a közöttük levő út hossza, akkor a szomszéd csúcs eddig

# ismert legrövidebb úthosszát erre az összegre módosítjuk.

if (distance := self.vertices[current].data[0] + float(edge_distance_to_neighbor)) < \

neighbor_vertex_obj.data[0]:

neighbor_vertex_obj.data = [distance, current]

# Miután az aktuális csúcs minden szomszédját megvizsgáltuk és aktulizáltuk a szomszédai legrövidebb

# távolság adatát és az odavezető megelőző csúcsot, az aktuális csúcsot megvizsgáltnak tekintjük és

# kivesszük a még meg nem látogatottak listájából.

unvisited.pop(current)

# Segédfüggvény

def shortest_path(end_vertex_label: str):

"""A start_vertex-től az argumentumként megadott végcsúcshoz vezető legrövidebb úton levő csúcsok

listáját adja vissza a csúcsok adatai alapján.

"""

path = []

path.append(end_vertex_label)

while previous_vertex := self.vertices[end_vertex_label].data[1]:

path.append(previous_vertex)

end_vertex_label = previous_vertex

return path[-1::-1]

# A visszatérési értékként szolgáló szótár előállítása, amelynek kulcsai a célcsúcsok címkéi, az

# ezekhez tartozó értékek olyan tuple konténerek, amelyek első eleme a célcsúcsig vezető legrövidebb

# út hossza, második eleme pedig a legrövidebb útat jelentő csúcsok listája.

shortest_distances_and_paths = {vx_label: (self.vertices[vx_label].data[0], shortest_path(vx_label))

for vx_label in self.vertices

if self.vertices[vx_label].data[0] != float('inf')}

return shortest_distances_and_paths

Az előző bejegyzésben említettük, hogy a csúcsokat célszerű osztállyal modellezni, mert ilyenkor a csúcs azonosító címkéjén felül egyéb adat is társítható a csúcshoz. Most erre is láthatunk példát, hiszen a legrövidebb úthosszt, és a megelőző csúcsot mint adatpárt a csúcs data attribútuma tárolja.

Az előbb nem említettük, hogy a Dijkstra algoritmus csak akkor működik helyesen, ha az élsúlyok nemnegatív valós számok. (Ha precízebbek akarunk lenni, akkor az élsúlyokra a feltétel, hogy értékkészletük monoton növekvő rendezett legyen, ami nem csak számokra lehet igaz.)

Ezért a metódushíváskor először ellenőrizzük, hogy fennáll-e az élsúlyokra a feltétel. Ahhoz, hogy a shortest_paths() metódus törzsében a logika áttekinthetősége az ellenőrzőkódokkal ne csökkenjen, az élsúlyok megfelelőségét egy dekorátorfüggvénybe szerveztük ki, és ezzel dekoráljuk a shortest_paths() metódust. A dekorátorfüggvény definíciója az alábbi:


class Graph:
    # Az előzőekben definiált metódusokat itt nem tüntettük fel.
    
    @staticmethod
    def check_edge_weight_values(fn):
        def inner(self, start_vertex_label: str):
            # Ellenőrizni kell, hogy minden élsúly szám-e, és nem negatív.
            try:
                for vertex_label, neightbor_set in self.neighbors.items():
                    for neighbor_label, edge_distance_to_neighbor in neightbor_set:
                        # Ha a konverzió nem lehetséges, akkor az azt jelenti, hogy a súly nem szám, vagy
                        # számnak nem tekinthető karaktersorozat a súly. Ekkor típushibát jelző kivétel dobódik.
                        weight_num = float(edge_distance_to_neighbor)
                        # Ha ugyan a súly szám, de negatív, akkor ezt jelző kivétel keletkezik.
                        if weight_num < 0:
                            raise ValueError('Minden élsúly nem negatív valós szám kell, hogy legyen')
            except (TypeError, ValueError):
                raise TypeError(
                    f'{vertex_label}-{neighbor_label} csúcsok közötti él súlya:{edge_distance_to_neighbor}. '
                    f'Minden él súlyának valós számnak kell lenni.')

            return fn(self, start_vertex_label)

        return inner

    @check_edge_weight_values
    def shortest_paths(self, start_vertex_label: str):...

class Graph:

# Az előzőekben definiált metódusokat itt nem tüntettük fel.

@staticmethod

def check_edge_weight_values(fn):

def inner(self, start_vertex_label: str):

# Ellenőrizni kell, hogy minden élsúly szám-e, és nem negatív.

try:

for vertex_label, neightbor_set in self.neighbors.items():

for neighbor_label, edge_distance_to_neighbor in neightbor_set:

# Ha a konverzió nem lehetséges, akkor az azt jelenti, hogy a súly nem szám, vagy

# számnak nem tekinthető karaktersorozat a súly. Ekkor típushibát jelző kivétel dobódik.

weight_num = float(edge_distance_to_neighbor)

# Ha ugyan a súly szám, de negatív, akkor ezt jelző kivétel keletkezik.

if weight_num < 0:

raise ValueError('Minden élsúly nem negatív valós szám kell, hogy legyen')

except (TypeError, ValueError):

raise TypeError(

f'{vertex_label}-{neighbor_label} csúcsok közötti él súlya:{edge_distance_to_neighbor}. '

f'Minden él súlyának valós számnak kell lenni.')

return fn(self, start_vertex_label)

return inner

@check_edge_weight_values

def shortest_paths(self, start_vertex_label: str):...

A fenti ellenőrzést végző kódsorból látható, hogy nem csak nemnegatív int és float számokat engedünk meg élsúlyként, hanem olyan karakterláncot is, amelyek nemnegatív int vagy float számot reprezentálnak.

Mindezek után a Graph valamint a Vertex osztály teljes definíciója az alábbi lesz:


class Vertex:
    def __init__(self, label, data=None):
        self.label = label
        self.data = data

    def __repr__(self):
        args = f'{self.label}, {self.data}' \
            if self.data is not None else f'{self.label}'
        return f'{type(self).__name__}({args})'


class Graph:
    def __init__(self):
        self.vertices: dict[str, Vertex] = dict()
        self.neighbors: dict[str, set[tuple[str, int | float]]] = defaultdict(set)

    def __str__(self):
        w = max(len(vname) for vname in self.neighbors)
        graph_string = []
        for vertex_label, neighbors in self.neighbors.items():
            nbrs = str(neighbors).strip("{}") if neighbors else ''
            graph_string.append(f'{vertex_label:{w}} {chr(0x279E)} {nbrs}\n')

        return ''.join(graph_string)

    def add_connection(self, start_vertex_label: str, end_vertex_label: str, weight=1):
        """A megadott kezdő- és végcsúcs közötti élt határozza meg a gráfban.
        Opcionálisan az élhez rendelhető egy súly is.
        Ha a csúcsok nem léteznek még, akkor azokat létrehozza.
        """
        # Hozzáadjuk az adott induló csúcshoz tartozó halmazhoz a végcsúcs és az él súlyából képzett párost.
        # Ha az adott csúcs még nincs a szótárban, akkor felveszi, és rögtön hozzárendel egy halmaz konténert.
        self.neighbors[start_vertex_label].add((end_vertex_label, weight))
        # Felvesszük a szomszédságot leíró szótárba a végcsúcsot, ha az nem létezik még, és amihez
        # rögtön hozzárendelünk egy halmaz konténert.
        self.neighbors[end_vertex_label]
        # A tényleges csúcs objektumokat is létrehozzuk és eltároljuk, ha még nem léteznek.
        if start_vertex_label not in self.vertices:
            self.vertices.update({start_vertex_label: Vertex(start_vertex_label)})
        if end_vertex_label not in self.vertices:
            self.vertices.update({end_vertex_label: Vertex(end_vertex_label)})

    def remove_edge(self, start_vertex_label: str, end_vertex_label: str):
        """A megadott kezdő- és végcsúcs közötti élt eltávolítja."""
        self.neighbors[start_vertex_label] = set(item for item in self.neighbors[start_vertex_label]
                                                 if item[0] != end_vertex_label)

    def remove_vertex(self, vertex_label: str):
        """A megadott csúcsot eltávolítja a gráfból."""
        # A csúcs objektumok közül eltávolítjuk a csúcsot.
        self.vertices.pop(vertex_label)
        # A szomszédságot leíró szótárból eltávolítjuk a megadott csúcsot.
        self.neighbors.pop(vertex_label)
        # Minden olyan csúcs esetén, amelynek szomszédja volt, kivesszük a szomszéd csúcsok közül.
        for vxl, nbs in self.neighbors.items():
            self.neighbors[vxl] = set(item for item in nbs if item[0] != vertex_label)

    def set_vertex_data(self, vertex_label, vertex_data):
        """Egy adott csúcshoz értéket rendel."""
        if vx := self.vertices.get(vertex_label):
            vx.data = vertex_data

    @staticmethod
    def check_edge_weight_values(fn):
        def inner(self, start_vertex_label: str):
            # Ellenőrizni kell, hogy minden élsúly szám-e, és nem negatív.
            try:
                for vertex_label, neightbor_set in self.neighbors.items():
                    for neighbor_label, edge_distance_to_neighbor in neightbor_set:
                        # Ha a konverzió nem lehetséges, akkor az azt jelenti, hogy a súly nem szám, vagy
                        # számnak nem tekinthető karaktersorozat a súly. Ekkor típushibát jelző kivétel dobódik.
                        weight_num = float(edge_distance_to_neighbor)
                        # Ha ugyan a súly szám, de negatív, akkor ezt jelző kivétel keletkezik.
                        if weight_num < 0:
                            raise ValueError('Minden élsúly nem negatív valós szám kell, hogy legyen')
            except (TypeError, ValueError):
                raise TypeError(
                    f'{vertex_label}-{neighbor_label} csúcsok közötti él súlya:{edge_distance_to_neighbor}. '
                    f'Minden él súlyának valós számnak kell lenni.')

            return fn(self, start_vertex_label)

        return inner

    @check_edge_weight_values
    def shortest_paths(self, start_vertex_label: str):
        """Visszaadja egy szótárban a megadott csúcstól számított legrövidebb út hosszát, valamint az
        összes csúcshoz vezető legrövidebb útvonalat.
        """
        # Minden kiinduló ponttól számított, eddig ismert legrövidebb úthosszat minden csúcsra végtelenre
        # állítjuk, hiszen ezeket kezdetben nem ismerjük még.
        for vertex_label in self.vertices:
            self.set_vertex_data(vertex_label, [float('inf'), None])
        # A kiinduló csúcs eddig ismert legrövidebb úthosszát 0-ra állítjuk, hiszen önmagától nulla távra van.
        self.set_vertex_data(start_vertex_label, [0, None])

        # Minden csúcsot még nem vizsgáltnak (nem látogatottnak) állítjuk be.
        unvisited: dict = {label: vertex for label, vertex in self.vertices.items()}

        while unvisited:
            # Egy olyan új aktuális vizsgálni kivánt csúcsot választunk a még nem látogatott csúcsok közül, amely
            # ezek közül a legrövidebb útvonallal rendelkezik.
            current = min(unvisited, key=lambda lbl: unvisited[lbl].data[0])

            # Az aktuális csúcsra kiszámítjuk a távolságot az összes nem látogatott szomszédjától.
            for neighbor, edge_distance_to_neighbor in self.neighbors[current]:
                if neighbor in unvisited:
                    neighbor_vertex_obj = self.vertices[neighbor]
                    # Ha a szomszéd csúcs eddig ismert legrövidebb úthossza nagyobb, mint a jelenlegi csúcs
                    # eddig ismert legrövidebb úthossza + a közöttük levő út hossza, akkor a szomszéd csúcs eddig
                    # ismert legrövidebb úthosszát erre az összegre módosítjuk.
                    if (distance := self.vertices[current].data[0] + float(edge_distance_to_neighbor)) < \
                            neighbor_vertex_obj.data[0]:
                        neighbor_vertex_obj.data = [distance, current]
            # Miután az aktuális csúcs minden szomszédját megvizsgáltuk és aktulizáltuk a szomszéd legrövidebb
            # távolság adatát és az odavezető megelőző csúcsot, az aktuális csúcsot megvizsgáltnak tekintjük és
            # kivesszük a még meg nem látogatottak listájából.
            unvisited.pop(current)

        # Segédfüggvény
        def shortest_path(end_vertex_label: str):
            """A start_vertex-től az argumentumként megadott végcsúcshoz vezető legrövidebb úton levő csúcsok
            listáját adja vissza a csúcsok adatai alapján.
            """
            path = []
            path.append(end_vertex_label)
            while previous_vertex := self.vertices[end_vertex_label].data[1]:
                path.append(previous_vertex)
                end_vertex_label = previous_vertex
            return path[-1::-1]
        # A visszatérési értékként szolgáló szótár előállítása, amelynek kulcsai a célcsúcsok címkéi, az
        # ezekhez tartozó értékek olyan tuple konténerek, amelyek első eleme a célcsúcsig vezető legrövidebb
        # út hossza, második eleme pedig a legrövidebb útat jelentő csúcsok listája.
        shortest_distances_and_paths = {vx_label: (self.vertices[vx_label].data[0], shortest_path(vx_label))
                                        for vx_label in self.vertices
                                        if self.vertices[vx_label].data[0] != float('inf')}

        return shortest_distances_and_paths

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

class Vertex:

def __init__(self, label, data=None):

self.label = label

self.data = data

def __repr__(self):

args = f'{self.label}, {self.data}' \

if self.data is not None else f'{self.label}'

return f'{type(self).__name__}({args})'

class Graph:

def __init__(self):

self.vertices: dict[str, Vertex] = dict()

self.neighbors: dict[str, set[tuple[str, int | float]]] = defaultdict(set)

def __str__(self):

w = max(len(vname) for vname in self.neighbors)

graph_string = []

for vertex_label, neighbors in self.neighbors.items():

nbrs = str(neighbors).strip("{}") if neighbors else ''

graph_string.append(f'{vertex_label:{w}} {chr(0x279E)} {nbrs}\n')

return ''.join(graph_string)

def add_connection(self, start_vertex_label: str, end_vertex_label: str, weight=1):

"""A megadott kezdő- és végcsúcs közötti élt határozza meg a gráfban.

Opcionálisan az élhez rendelhető egy súly is.

Ha a csúcsok nem léteznek még, akkor azokat létrehozza.

"""

# Hozzáadjuk az adott induló csúcshoz tartozó halmazhoz a végcsúcs és az él súlyából képzett párost.

# Ha az adott csúcs még nincs a szótárban, akkor felveszi, és rögtön hozzárendel egy halmaz konténert.

self.neighbors[start_vertex_label].add((end_vertex_label, weight))

# Felvesszük a szomszédságot leíró szótárba a végcsúcsot, ha az nem létezik még, és amihez

# rögtön hozzárendelünk egy halmaz konténert.

self.neighbors[end_vertex_label]

# A tényleges csúcs objektumokat is létrehozzuk és eltároljuk, ha még nem léteznek.

if start_vertex_label not in self.vertices:

self.vertices.update({start_vertex_label: Vertex(start_vertex_label)})

if end_vertex_label not in self.vertices:

self.vertices.update({end_vertex_label: Vertex(end_vertex_label)})

def remove_edge(self, start_vertex_label: str, end_vertex_label: str):

"""A megadott kezdő- és végcsúcs közötti élt eltávolítja."""

self.neighbors[start_vertex_label] = set(item for item in self.neighbors[start_vertex_label]

if item[0] != end_vertex_label)

def remove_vertex(self, vertex_label: str):

"""A megadott csúcsot eltávolítja a gráfból."""

# A csúcs objektumok közül eltávolítjuk a csúcsot.

self.vertices.pop(vertex_label)

# A szomszédságot leíró szótárból eltávolítjuk a megadott csúcsot.

self.neighbors.pop(vertex_label)

# Minden olyan csúcs esetén, amelynek szomszédja volt, kivesszük a szomszéd csúcsok közül.

for vxl, nbs in self.neighbors.items():

self.neighbors[vxl] = set(item for item in nbs if item[0] != vertex_label)

def set_vertex_data(self, vertex_label, vertex_data):

"""Egy adott csúcshoz értéket rendel."""

if vx := self.vertices.get(vertex_label):

vx.data = vertex_data

@staticmethod

def check_edge_weight_values(fn):

def inner(self, start_vertex_label: str):

# Ellenőrizni kell, hogy minden élsúly szám-e, és nem negatív.

try:

for vertex_label, neightbor_set in self.neighbors.items():

for neighbor_label, edge_distance_to_neighbor in neightbor_set:

# Ha a konverzió nem lehetséges, akkor az azt jelenti, hogy a súly nem szám, vagy

# számnak nem tekinthető karaktersorozat a súly. Ekkor típushibát jelző kivétel dobódik.

weight_num = float(edge_distance_to_neighbor)

# Ha ugyan a súly szám, de negatív, akkor ezt jelző kivétel keletkezik.

if weight_num < 0:

raise ValueError('Minden élsúly nem negatív valós szám kell, hogy legyen')

except (TypeError, ValueError):

raise TypeError(

f'{vertex_label}-{neighbor_label} csúcsok közötti él súlya:{edge_distance_to_neighbor}. '

f'Minden él súlyának valós számnak kell lenni.')

return fn(self, start_vertex_label)

return inner

@check_edge_weight_values

def shortest_paths(self, start_vertex_label: str):

"""Visszaadja egy szótárban a megadott csúcstól számított legrövidebb út hosszát, valamint az

összes csúcshoz vezető legrövidebb útvonalat.

"""

# Minden kiinduló ponttól számított, eddig ismert legrövidebb úthosszat minden csúcsra végtelenre

# állítjuk, hiszen ezeket kezdetben nem ismerjük még.

for vertex_label in self.vertices:

self.set_vertex_data(vertex_label, [float('inf'), None])

# A kiinduló csúcs eddig ismert legrövidebb úthosszát 0-ra állítjuk, hiszen önmagától nulla távra van.

self.set_vertex_data(start_vertex_label, [0, None])

# Minden csúcsot még nem vizsgáltnak (nem látogatottnak) állítjuk be.

unvisited: dict = {label: vertex for label, vertex in self.vertices.items()}

while unvisited:

# Egy olyan új aktuális vizsgálni kivánt csúcsot választunk a még nem látogatott csúcsok közül, amely

# ezek közül a legrövidebb útvonallal rendelkezik.

current = min(unvisited, key=lambda lbl: unvisited[lbl].data[0])

# Az aktuális csúcsra kiszámítjuk a távolságot az összes nem látogatott szomszédjától.

for neighbor, edge_distance_to_neighbor in self.neighbors[current]:

if neighbor in unvisited:

neighbor_vertex_obj = self.vertices[neighbor]

# Ha a szomszéd csúcs eddig ismert legrövidebb úthossza nagyobb, mint a jelenlegi csúcs

# eddig ismert legrövidebb úthossza + a közöttük levő út hossza, akkor a szomszéd csúcs eddig

# ismert legrövidebb úthosszát erre az összegre módosítjuk.

if (distance := self.vertices[current].data[0] + float(edge_distance_to_neighbor)) < \

neighbor_vertex_obj.data[0]:

neighbor_vertex_obj.data = [distance, current]

# Miután az aktuális csúcs minden szomszédját megvizsgáltuk és aktulizáltuk a szomszéd legrövidebb

# távolság adatát és az odavezető megelőző csúcsot, az aktuális csúcsot megvizsgáltnak tekintjük és

# kivesszük a még meg nem látogatottak listájából.

unvisited.pop(current)

# Segédfüggvény

def shortest_path(end_vertex_label: str):

"""A start_vertex-től az argumentumként megadott végcsúcshoz vezető legrövidebb úton levő csúcsok

listáját adja vissza a csúcsok adatai alapján.

"""

path = []

path.append(end_vertex_label)

while previous_vertex := self.vertices[end_vertex_label].data[1]:

path.append(previous_vertex)

end_vertex_label = previous_vertex

return path[-1::-1]

# A visszatérési értékként szolgáló szótár előállítása, amelynek kulcsai a célcsúcsok címkéi, az

# ezekhez tartozó értékek olyan tuple konténerek, amelyek első eleme a célcsúcsig vezető legrövidebb

# út hossza, második eleme pedig a legrövidebb útat jelentő csúcsok listája.

shortest_distances_and_paths = {vx_label: (self.vertices[vx_label].data[0], shortest_path(vx_label))

for vx_label in self.vertices

if self.vertices[vx_label].data[0] != float('inf')}

return shortest_distances_and_paths

Tesztelésre egy gyakorlati példát választottunk, amelyben néhány nagyváros mint csúcs és a közöttük levő, közúton mért távolság mint élsúly szerepel kilométerben. Ezt mutatja az ábra:

Az alábbi tesztprogramban egyrészt láthatjuk megjelenítve a szomszédsági viszonyokat, másrészt azt, hogy egy kiválasztott várostól a többi városba milyen hosszú a legrövidebb út, és az milyen városokon keresztül haladva érhető el.


# TESZT

class Town(Vertex):
    def __init__(self, name, num_of_inhabitants=None):
        super().__init__(name)
        self.name = name
        self.total_inhabitants = num_of_inhabitants

class Country(Graph): pass

country = Country() # Létrehozzuk a városokat tartalmazó országot modellező gráf példányt.

# Városok és közöttük levő távolságok, amelyek a gráf csúcsai és a közöttük levő él súlyai lesznek.
edge_strings = ['Budapest-Miskolc-190', 'Budapest-Debrecen-231', 'Budapest-Szeged-175', 'Budapest-Pécs-232',
                'Budapest-Sopron-217', 'Budapest-Győr-121', 'Miskolc-Debrecen-114', 'Debrecen-Szeged-226',
                'Szeged-Pécs-190', 'Pécs-Sopron-295', 'Sopron-Győr-97', 'Győr-Miskolc-328']

# A városok közötti útvonalakat leíró gráf irányítatlan, ezért mindkét irányt (a gráf éleit) meghatározzuk.
forward_directions = [edge_str.split('-') for edge_str in edge_strings]
reverse_directons = [[town2, town1, km] for town1, town2, km in forward_directions]

# Felépítjük a gráfot az összeköttetések alapján.
for towns_and_distance in forward_directions+reverse_directons:
    country.add_connection(*towns_and_distance)

# Megjelenítjük a gráfot leíró szomszédsági kapcsolatokat.
print(country)

# Eredmény:
# Budapest ➞ ('Szeged', '175'), ('Sopron', '217'), ('Debrecen', '231'), ('Pécs', '232'), ('Miskolc', '190'), ('Győr', '121')
# Miskolc  ➞ ('Budapest', '190'), ('Győr', '328'), ('Debrecen', '114')
# Debrecen ➞ ('Miskolc', '114'), ('Budapest', '231'), ('Szeged', '226')
# Szeged   ➞ ('Debrecen', '226'), ('Budapest', '175'), ('Pécs', '190')
# Pécs     ➞ ('Szeged', '190'), ('Sopron', '295'), ('Budapest', '232')
# Sopron   ➞ ('Budapest', '217'), ('Pécs', '295'), ('Győr', '97')
# Győr     ➞ ('Budapest', '121'), ('Miskolc', '328'), ('Sopron', '97')

# Lekérjük egy kiindulási városból az összes többi városhoz vezető legrövidebb útvonal hosszát, és magát az útvonalat.
departure_city = 'Szeged'
for destination_city, travel_data in country.shortest_paths(departure_city).items():
    if departure_city != destination_city:
        print(f'{departure_city} - {destination_city} útvonal legrövidebb távolság {travel_data[0]:.0f}km, '
              f'útvonal: {" ⟶ ".join(travel_data[1])}')
# Eredmény:
# Szeged - Budapest útvonal legrövidebb távolság 175km, útvonal: Szeged ⟶ Budapest
# Szeged - Miskolc útvonal legrövidebb távolság 340km, útvonal: Szeged ⟶ Debrecen ⟶ Miskolc
# Szeged - Debrecen útvonal legrövidebb távolság 226km, útvonal: Szeged ⟶ Debrecen
# Szeged - Pécs útvonal legrövidebb távolság 190km, útvonal: Szeged ⟶ Pécs
# Szeged - Sopron útvonal legrövidebb távolság 392km, útvonal: Szeged ⟶ Budapest ⟶ Sopron
# Szeged - Győr útvonal legrövidebb távolság 296km, útvonal: Szeged ⟶ Budapest ⟶ Győr

# TESZT

class Town(Vertex):

def __init__(self, name, num_of_inhabitants=None):

super().__init__(name)

self.name = name

self.total_inhabitants = num_of_inhabitants

class Country(Graph): pass

country = Country() # Létrehozzuk a városokat tartalmazó országot modellező gráf példányt.

# Városok és közöttük levő távolságok, amelyek a gráf csúcsai és a közöttük levő él súlyai lesznek.

edge_strings = ['Budapest-Miskolc-190', 'Budapest-Debrecen-231', 'Budapest-Szeged-175', 'Budapest-Pécs-232',

'Budapest-Sopron-217', 'Budapest-Győr-121', 'Miskolc-Debrecen-114', 'Debrecen-Szeged-226',

'Szeged-Pécs-190', 'Pécs-Sopron-295', 'Sopron-Győr-97', 'Győr-Miskolc-328']

# A városok közötti útvonalakat leíró gráf irányítatlan, ezért mindkét irányt (a gráf éleit) meghatározzuk.

forward_directions = [edge_str.split('-') for edge_str in edge_strings]

reverse_directons = [[town2, town1, km] for town1, town2, km in forward_directions]

# Felépítjük a gráfot az összeköttetések alapján.

for towns_and_distance in forward_directions+reverse_directons:

country.add_connection(*towns_and_distance)

# Megjelenítjük a gráfot leíró szomszédsági kapcsolatokat.

print(country)

# Eredmény:

# Budapest ➞ ('Szeged', '175'), ('Sopron', '217'), ('Debrecen', '231'), ('Pécs', '232'), ('Miskolc', '190'), ('Győr', '121')

# Miskolc ➞ ('Budapest', '190'), ('Győr', '328'), ('Debrecen', '114')

# Debrecen ➞ ('Miskolc', '114'), ('Budapest', '231'), ('Szeged', '226')

# Szeged ➞ ('Debrecen', '226'), ('Budapest', '175'), ('Pécs', '190')

# Pécs ➞ ('Szeged', '190'), ('Sopron', '295'), ('Budapest', '232')

# Sopron ➞ ('Budapest', '217'), ('Pécs', '295'), ('Győr', '97')

# Győr ➞ ('Budapest', '121'), ('Miskolc', '328'), ('Sopron', '97')

# Lekérjük egy kiindulási városból az összes többi városhoz vezető legrövidebb útvonal hosszát, és magát az útvonalat.

departure_city = 'Szeged'

for destination_city, travel_data in country.shortest_paths(departure_city).items():

if departure_city != destination_city:

print(f'{departure_city} - {destination_city} útvonal legrövidebb távolság {travel_data[0]:.0f}km, '

f'útvonal: {" ⟶ ".join(travel_data[1])}')

# Eredmény:

# Szeged - Budapest útvonal legrövidebb távolság 175km, útvonal: Szeged ⟶ Budapest

# Szeged - Miskolc útvonal legrövidebb távolság 340km, útvonal: Szeged ⟶ Debrecen ⟶ Miskolc

# Szeged - Debrecen útvonal legrövidebb távolság 226km, útvonal: Szeged ⟶ Debrecen

# Szeged - Pécs útvonal legrövidebb távolság 190km, útvonal: Szeged ⟶ Pécs

# Szeged - Sopron útvonal legrövidebb távolság 392km, útvonal: Szeged ⟶ Budapest ⟶ Sopron

# Szeged - Győr útvonal legrövidebb távolság 296km, útvonal: Szeged ⟶ Budapest ⟶ Győr

E bejegyzés témájához a Python tudásépítés lépésről lépésre című e-könyv következő részei kapcsolódnak különösen: a „Minden objektum!” fejezet „Objektumok létrehozásának módjai” alfejezet, „Konstruktorok” cím, a „Műveletek” fejezet „Konténerépítés” alfejezet, a „Beépített típusok nyilvános metódusai”, és a „Képességfejlesztés – függvénydekorátorok” fejezet.

Legrövidebb út meghatározása gráfokban

Érdekel a Python tudásépítés lépésről lépésre az alapoktól az első asztali alkalmazásig című e-könyv.