Dijkstrův algoritmus v Pythonu

Honza

Dijkstrův algoritmus v Pythonu
« kdy: 26. 01. 2017, 17:50:22 »
Ahoj,

mám do školy udělat implementaci dijsktrova algoritmu a úplně si nevím rady s jednou věcí - mám tento kód napsaný


Kód: [Vybrat]
class Vertex:
    def __init__(self, id, name):
        self.id = id
        self.name = name


class Edge:
    def __init__(self, source, target, weight):
        self.source = source
        self.target = target
        self.weight = weight

class Dijkstra:
    def __init__(self):
        self.vert_dict = {}
        self.num_vertices = 0
    def computePath(self, sourceId):
        pass

    def getShortestPathTo(self, targetId):
        pass

    def createGraph(self, vertexes, edgesToVertexes):
        self.graph = {}
        for vert in vertexes:
            self.graph[vert] = []
        for edge in edgesToVertexes:
            self.graph[edge.source].append(edge)

    def resetDijkstra(self):
        pass

    def getVertexes(self):
        return self.vert_dict.keys()

A popis metod u třídy Dijkstra

createGraph(self, vertexes, edgesToVertexes) - metoda vytvoří graf ze zadaných vrcholů - toto myslím, že mám dobře
getVertexes(self) - metoda vrátí vrcholy, nad kterými je možné provést Dijkstrův algoritmus. TJ vrcholy, které jsou vytvořeny pomocí metody init - to si také myslím, že mám dobře
computePath(self, sourceId) - metoda nalezne nejkraští cesty ze zadaného vrcholu do všech vrcholů v grafu. Metoda nic nevrací, ale po skončení operace by měly mít všechny vrcholy vyplněnou proměnou minDistance, která reprezentuje minimální vzdálenost o zadaného vrcholu - tohle nevím jak udělat. Mohl by mi prosím někdo poradit? :)
« Poslední změna: 27. 01. 2017, 09:17:07 od Petr Krčmář »


Re:Dijkstrův algoritmus - python
« Odpověď #1 kdy: 26. 01. 2017, 18:15:02 »
Takže jediná věc, co ti z domácího úkolu chybí, je ten domácí úkol? ;)

Zamysli se, co budeš potřebovat. Co třebas nějakou datovou strukturu, kde si budeš držet zatím nehotové vrcholy?

Jenda

Re:Dijkstrův algoritmus - python
« Odpověď #2 kdy: 26. 01. 2017, 18:18:20 »
computePath(self, sourceId) - metoda nalezne nejkraští cesty ze zadaného vrcholu do všech vrcholů v grafu. Metoda nic nevrací, ale po skončení operace by měly mít všechny vrcholy vyplněnou proměnou minDistance, která reprezentuje minimální vzdálenost o zadaného vrcholu - tohle nevím jak udělat. Mohl by mi prosím někdo poradit? :)
Vrchol už nesmí být obyčejný seznam, ale třída, která bude mít:

  * číslo (na začátku +nekonečno, -1 nebo tak něco) udávající minimální vzdálenost
  * seznam sousedů/hran stejně jako to máš teď.

A potom tvoje funkce vždycky nalije vrcholy do nějakého pomocného pole (příp. haldy pro lepší složitost), updatne všem sousedům tato čísla, vytáhne z pomocného pole vrchol s nejmenším číslem a opakuje.

Honza

Re:Dijkstrův algoritmus - python
« Odpověď #3 kdy: 26. 01. 2017, 18:28:57 »
Myslel jsem to, tak že to vytvoření grafu a vracení vrcholů mám v pořádku (alespoň se domnívám) :)

Ok, takže bych to viděl na nějakou frontu? Respektive nějakou prioritní frontu, která mi to seřadí podle hran s nejmenší cestou?

Honza

Re:Dijkstrův algoritmus - python
« Odpověď #4 kdy: 26. 01. 2017, 18:34:58 »
Já to chápu takhle -

V počátečním uzlu (N) budu mít cestu nejmenší - 0 a předka None, pak porovnám váhu všech hran a vydám se tou nejmenší, kde nastavím jako váhu 0 + 5 = 5, předek N. Poté znovu porovnám od tohoto uzlu (M) nejmenší hranu (tady bude asi problém toho, aby to nebyl ta hrany, po které jsem přijel) a opět jí přiřadím váhu 5 + 2 = 7, předek bude M...


Honza

Re:Dijkstrův algoritmus - python
« Odpověď #5 kdy: 26. 01. 2017, 18:54:24 »
Já ten algoritmus chápu, kdybych ho měl nakreslit na papíře jak se to chová, tak je to v pořádku.

Pro mě je právě ten nejhorší problém to pak dostat do kódu :/ to mi prostě vůbec nejde... Kdyby vám mohl poprosit právě, o nějaký návod krok za krokem, jak to vytvořit. Něco jako 1) potřebuješ frontu, za 2) proiteruješ jí, 3)...

Jenda

Re:Dijkstrův algoritmus - python
« Odpověď #6 kdy: 26. 01. 2017, 18:55:30 »
Myslel jsem to, tak že to vytvoření grafu a vracení vrcholů mám v pořádku (alespoň se domnívám) :)
Je správně, ale zadání po tobě vyžaduje, aby to kromě seznamu sousedů umělo držet i číslo, což bych právě řešil přes tu třídu.

V počátečním uzlu (N) budu mít cestu nejmenší - 0 a předka None, pak porovnám váhu všech hran a vydám se tou nejmenší, kde nastavím jako váhu 0 + 5 = 5, předek N. Poté znovu porovnám od tohoto uzlu (M) nejmenší hranu
To právě nebude fungovat. Mějme vrcholy A, B, C a hrany
Kód: [Vybrat]
A → B (2)
A → C (2)
A → C (3)
(a začínáme v A). Ty se vydáš do B, nastavíš cenu na 2, a z B se vydáš do C, tam nastavíš cenu na 4, ale správná cena je 3. Proto nesmíš jít po nejlevnější hraně z aktuálního vrcholu, ale z nejlevnějšího vrcholu - a proto tam máš tu haldu.

Pro mě je právě ten nejhorší problém to pak dostat do kódu :/ to mi prostě vůbec nejde... Kdyby vám mohl poprosit právě, o nějaký návod krok za krokem, jak to vytvořit.
Začal bych tím, že přepíšeš ten pseudokód z Wikipedie do Pythonu ;)

gll

Re:Dijkstrův algoritmus - python
« Odpověď #7 kdy: 26. 01. 2017, 18:57:29 »
 zahodil bych třídu Vector.  Stačí čísla vrcholů. Nestačí reprezentovat hrany jako n-tice? Ta tvá reprezentace je strašné plýtvání.

smíte používat nějakou knihovnu pro haldu?

pokud smíte používat libovolnou knihovnu, celé bych to zahodil a použil igraph

gll

Re:Dijkstrův algoritmus - python
« Odpověď #8 kdy: 26. 01. 2017, 18:58:42 »
oprava:

zahodil bych třídu Vertex.

Jenda

Re:Dijkstrův algoritmus - python
« Odpověď #9 kdy: 26. 01. 2017, 20:07:57 »
zahodil bych třídu Vertex.
Jé, to jsem si nevšiml, do ní přece může uložit to číslo, které požaduje zadání.

Stačí čísla vrcholů.
A někam musí ukládat ty vzdálenosti - může to dávat do druhého seznamu. A tady se dá vybrat, jestli to právě mít „správně“ (třída), nebo o něco menší a rychlejší (seznamy)

Honza

Re:Dijkstrův algoritmus - python
« Odpověď #10 kdy: 26. 01. 2017, 20:32:52 »
S tím pseudokódem nevím - nevím jak ho dát do Pythonu...

Laboroval jsem do teď nad tím a fakt nevím, asi by bylo dobré si zopakovat celý předmět od začátku... :/

Jinak ty třídy apod. musí vypadat přesně tak, jak to tady mám napsané. Žádné knihovny používat nemůžeme a taky musíme  místo haldy používat prioritní frontu.

gll

Re:Dijkstrův algoritmus - python
« Odpověď #11 kdy: 26. 01. 2017, 20:40:23 »
zahodil bych třídu Vertex.
Jé, to jsem si nevšiml, do ní přece může uložit to číslo, které požaduje zadání.

Stačí čísla vrcholů.
A někam musí ukládat ty vzdálenosti - může to dávat do druhého seznamu. A tady se dá vybrat, jestli to právě mít „správně“ (třída), nebo o něco menší a rychlejší (seznamy)

čísla vrcholů jsou indexy listu, vzdálenosti jsou hodnoty. Není důvod číslovat vrcholy jinak než od nuly.

Jako vstup lze zadat jen počet vrcholů a hrany. Není třeba vrcholy vyjmenovávat. Tak to má i igraph.

gll

Re:Dijkstrův algoritmus - python
« Odpověď #12 kdy: 27. 01. 2017, 12:19:59 »
Žádné knihovny používat nemůžeme a taky musíme  místo haldy používat prioritní frontu.

to je to stejné, prioritní fronta se většinou implementuje pomocí haldy. nesmíte používat ani vestavěné knihovny?

třeba zde je pěkné řešení. těžko se dá vymyslet něco lepšího.

https://gist.github.com/kachayev/5990802

Můžeš to zkusit naroubovat na tu svou kostru. defaultdict se dá nahradit a heapq s trochou úsilí také.

lopata

Re:Dijkstrův algoritmus - python
« Odpověď #13 kdy: 27. 01. 2017, 12:46:07 »
Žádné knihovny používat nemůžeme a taky musíme  místo haldy používat prioritní frontu.

Neznám zadání, nicméně pokud nemáš předepsanou interní formu reprezentace grafu, můžeš použít adjacency matrix, potom pro Dijkstru prioritní frontu nepotřebuješ: https://gist.github.com/shintoishere/f0fa40fe1134b20e7729
Složitost to má O(V^2), kde V je počet vrcholů, takže se to prakticky hodí jen pro grafy, které mají hodně hran a málo vrcholů.

gll

Re:Dijkstrův algoritmus v Pythonu
« Odpověď #14 kdy: 27. 01. 2017, 14:02:30 »
Kód: [Vybrat]
def dijkstra(edges, f, t):
    g = {}
    for l,r,c in edges:
        g.setdefault(l, []).append((c,r))
    q, seen = [(0,f,())], set()
    while q:
        (cost,v1,path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if v1 == t: return (cost, path)
            for c, v2 in g.get(v1, ()):
                if v2 not in seen:
                    heappush(q, (cost+c, v2, path))
    return float("inf")


# následují funkce převzaté z heapq.py


def heappush(heap, item):
    heap.append(item)
    _siftdown(heap, 0, len(heap)-1)


def heappop(heap):
    lastelt = heap.pop()
    if heap:
        returnitem = heap[0]
        heap[0] = lastelt
        _siftup(heap, 0)
        return returnitem
    return lastelt

def _siftup(heap, pos):
    endpos = len(heap)
    startpos = pos
    newitem = heap[pos]
    childpos = 2*pos + 1
    while childpos < endpos:
        rightpos = childpos + 1
        if rightpos < endpos and not heap[childpos] < heap[rightpos]:
            childpos = rightpos
        heap[pos] = heap[childpos]
        pos = childpos
        childpos = 2*pos + 1
    heap[pos] = newitem
    _siftdown(heap, startpos, pos)


def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem

nahradil jsem v tom řešení z https://gist.github.com/kachayev/5990802 importované moduly vloženým kódem. Můžeš to zkusit nějak obfuskovat, aby to vypadalo jako tvůj výtvor.