Vytvoření grafu - Dijkstra – Python – Fórum – Programujte.com

Ahoj,

řeším takovou menší úlohu do školy a to spočívá v sestavení dijsktrova algoritmu.

Mám tento kód

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):

A metodu createGraph, která ze zadaných vrcholů vytvoří graf. Můžete mi prosím poradit (popř. pouze navést či ukázat jak na to)?

Díky  [:)]

#1 Lukáš
A metodu createGraph, která ze zadaných vrcholů vytvoří graf.

Co tym presne myslis? Mozno by pomohlo, keby si nam povedal, ako vyzera vstup do tvojho programu.

#2 Matho
No zatím mám pouze tuto úlohu

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):

    def computePath(self, sourceId):
        pass

    def getShortestPathTo(self, targetId):
        pass

    def createGraph(self, vertexes, edgesToVertexes):
        pass

    def resetDijkstra(self):
        pass

    def getVertexes(self):
        pass

A toto zadání:

createGraph(self, vertexes, edgesToVertexes) - metoda vytvoří graf ze zadaných vrcholů. Vertexes je pole objektů typu Vertex a edgesToVertexes je pole typu Edge.
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.
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.
getShortestPathTo(self,targetId) - metoda vrátí list vrcholů, přes které vede z vrcholu, nad kterými byla spuštěna operace computePath do vrcholu specifikovaného v targetId.
resetDijkstra(self) - tato metoda vyresetuje aktuální výsledky po průchodu dijkstrovým algoritmem. Metoda nerozpojí či nezahodí graf, pouze ho vrátí do stavu, v jakém byl před operací computePath

Respektive tady mám vstup:

#New Dijkstra created
dijkstra = Dijkstra()
#Graph created
dijkstra.createGraph(vertexes,edges)
#Getting all vertexes
dijkstraVertexes = dijkstra.getVertexes()
#Computing min distance for each vertex in graph
for vertexToCompute in dijkstraVertexes:
    dijkstra.computePath(vertexToCompute.id)
    print('Printing min distance from vertex:'+str(vertexToCompute.name))
    #Print minDitance from current vertex to each other
    for vertex in dijkstraVertexes:
        print('Min distance to:'+str(vertex.name)+' is: '+str(vertex.minDistance))
    #Reset Dijkstra between counting
    dijkstra.resetDijkstra()
#Distance with path
for vertexToCompute in dijkstraVertexes:
    dijkstra.computePath(vertexToCompute.id)
    print('Printing min distance from vertex:'+str(vertexToCompute.name))
    #Print minDitance and path from current vertex to each other
    for vertex in dijkstraVertexes:
        print('Min distance to:'+str(vertex.name)+' is: '+str(vertex.minDistance))
        print('Path is:',end=" ")
        #Get shortest path to target vertex
        path = dijkstra.getShortestPathTo(vertex.id)
        for vertexInPath in path:
            print(str(vertexInPath.name),end=" ")
        print()
    #Reset Dijkstra between counting
    dijkstra.resetDijkstra()

#1 Lukáš

https://networkx.github.io/

To je nějaká knihovna? 

Bohužel to nemohu použít, musím se držet zadání

createGraph(self, vertexes, edgesToVertexes) - metoda vytvoří graf ze zadaných vrcholů. Vertexes je pole objektů typu Vertex a edgesToVertexes je pole typu Edge.

 To podla mna iba znamena, ze tvoja trieda Dijkstra bude mat dva atributy (polia alebo mnoziny) Vertices a Edges, do ktorych vo funkcii createGraph priradis dane hodnoty. Nic viac by som za tym nevidel.

Ak budes potrebovat pomoc s niecim dalsim, tak napis.

#7 Matho
Mohl bych tě poprosit i o kód? nějak si to takto nedovedu představit... :)

class Dijkstra:
    self.vertices = None
    self.edges = None

    def createGraph(self, vertexes, edgesToVertexes):
        self.vertices = vertexes
        self.edges = edgesToVertexes

Upozornujem, ze je toto forum moze opravujuci tvojho predmetu sledovat, preto je lepsie ziadat o rady ku konkretnemu kodu ako ziadat o vytvorenie noveho kodu. Ak mas problemy so zakladmi, doporucujem nastudovat si Python dokumentaciu.

#8 Lukáš
Nemám ani řádek, udělejte za mě úkol. Už je po Vánocích ;-)

Když funkce createGraph dostane vrcholy a hrany, tak bych z nich asi vytvořil ten graf, ne? Minimálně třeba nějak takhle:

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

Díky, už se chytám :)