Vytvoření grafu - Dijkstra – Python – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Lukáš
~ Anonymní uživatel
289 příspěvků
9. 1. 2017   #1
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:1e02:9112:11d4:a...–
Reklama
Reklama
Matho
~ Anonymní uživatel
5 příspěvků
9. 1. 2017   #2
-
0
-

#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.

Nahlásit jako SPAM
IP: 147.251.208.–
Lukáš
~ Anonymní uživatel
289 příspěvků
9. 1. 2017   #3
-
0
-

#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

Nahlásit jako SPAM
IP: 2001:718:1e02:9112:11d4:a...–
Lukáš
~ Anonymní uživatel
289 příspěvků
9. 1. 2017   #4
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:1e02:9112:11d4:a...–
Pavel
~ Anonymní uživatel
274 příspěvků
9. 1. 2017   #5
-
0
-

#1 Lukáš

https://networkx.github.io/

Nahlásit jako SPAM
IP: 178.72.234.–
Lukáš
~ Anonymní uživatel
289 příspěvků
9. 1. 2017   #6
-
0
-

To je nějaká knihovna? 

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

Nahlásit jako SPAM
IP: 2001:718:1e02:9112:11d4:a...–
Matho
~ Anonymní uživatel
5 příspěvků
10. 1. 2017   #7
-
0
-

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.

Nahlásit jako SPAM
IP: 147.251.208.–
Lukáš
~ Anonymní uživatel
289 příspěvků
10. 1. 2017   #8
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:1e02:9112:bc88:7...–
Matho
~ Anonymní uživatel
5 příspěvků
10. 1. 2017   #9
-
0
-

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.

Nahlásit jako SPAM
IP: 147.251.51.–
gna
~ Anonymní uživatel
406 příspěvků
10. 1. 2017   #10
-
0
-

#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)
Nahlásit jako SPAM
IP: 213.211.51.–
Lukáš
~ Anonymní uživatel
289 příspěvků
11. 1. 2017   #11
-
0
-

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

Nahlásit jako SPAM
IP: 2001:718:1e02:9112:bc88:7...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 10 hostů

Podobná vlákna

Analýza grafů — založil Spectator

Souvislost grafu — založil goesss84

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý