Datei:DijkstraDemo.gif
aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen
Zur Suche springen
DijkstraDemo.gif (521 × 518 Pixel, Dateigröße: 5,94 MB, MIME-Typ: image/gif, Endlosschleife, 127 Bilder, 1 min 4 s)
Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.
Beschreibung
BeschreibungDijkstraDemo.gif |
English: A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering. Blue lines indicate where relaxing happens. |
Datum | |
Quelle | Eigenes Werk |
Urheber | Shiyu Ji |
Python 3 Code
'''
Dijkstra's shortest path covering (SVG) using priority queue.
Firstly use this code to generate SVG frames.
Then transform to bitmaps and convert to GIF.
'''
# range size
N = 500
margin = 20
def norm(px, py):
return ((px[0]-py[0])**2+(px[1]-py[1])**2)**.5
def saveToSVG(nFrames, points, edges, firmed, relaxing):
f = open('demo_'+'0'*(3-len(str(nFrames)))+str(nFrames)+'.svg', 'w')
f.write("<svg xmlns=\"http://www.w3.org/2000/svg\" version=\"1.1\">\n")
for p in points:
f.write("<circle cx=\"" +str(p[0]+margin)+ "\" cy=\""+ str(N-p[1]+margin) +"\" r=\"5\" fill=\"white\" stroke=\"black\"/>\n")
for i in range(len(edges)):
for j in edges[i]:
f.write("<line x1=\"" +str(points[i][0]+margin)+ "\" y1=\""+ str(N-points[i][1]+margin) +"\" x2=\"" + str(points[j][0]+margin) + "\" y2=\"" + str(N-points[j][1]+margin) + "\" stroke=\"grey\" stroke-width=\".5\"/>\n")
for L in firmed:
f.write("<line x1=\"" +str(L[0][0]+margin)+ "\" y1=\""+ str(N-L[0][1]+margin) +"\" x2=\"" + str(L[1][0]+margin) + "\" y2=\"" + str(N-L[1][1]+margin) + "\" stroke=\"red\" stroke-width=\"5\"/>\n")
for L in relaxing:
f.write("<line x1=\"" +str(L[0][0]+margin)+ "\" y1=\""+ str(N-L[0][1]+margin) +"\" x2=\"" + str(L[1][0]+margin) + "\" y2=\"" + str(N-L[1][1]+margin) + "\" stroke=\"blue\" stroke-width=\"5\"/>\n")
f.write("</svg>\n")
f.close()
def generatePoints(n):
import random as r
r.seed(10)
res = []
for i in range(n):
pt = [r.randint(0,N) for _ in [0, 1]]
if pt not in res:
res += [pt]
return res
# heuristic: neighbor with radius e.g. N/3
def generateEdges(n, points):
import random as r
r.seed(10)
edges = []
for i in range(n):
dst = []
for j in range(n):
if i!=j and norm(points[i], points[j]) < N/3:
dst.append(j);
edges.append(dst)
return edges
def dijkstra(n, points, edges):
nframe = 0
dist = [float("inf") for i in range(n)]
prev = [-1 for _ in range(n)]
cover = []
import heapq
dist[0] = 0.0
heap = [[dist[i], i] for i in range(n)]
while len(heap)>0:
u = heap[0][1]
if prev[u]!=-1:
cover.append([points[prev[u]], points[u]])
saveToSVG(nframe, points, edges, cover, [])
nframe+=1
heapq.heappop(heap)
for i in edges[u]:
if i!=u and dist[i] > dist[u] + norm(points[i], points[u]):
dist[i] = dist[u] + norm(points[i], points[u])
prev[i] = u
for j in range(len(heap)):
if heap[j][1] == i:
heap[j][0] = dist[i]
break
heapq.heapify(heap)
saveToSVG(nframe, points, edges, cover, [[points[u], points[i]]])
nframe+=1
return dist, prev
# test 50 points temporarily
n = 50
pts = generatePoints(n)
es = generateEdges(n, pts)
dijkstra(n, pts, es)
Lizenz
Ich, der Urheber dieses Werkes, veröffentliche es unter der folgenden Lizenz:
Diese Datei ist lizenziert unter der Creative-Commons-Lizenz „Namensnennung – Weitergabe unter gleichen Bedingungen 4.0 international“.
- Dieses Werk darf von dir
- verbreitet werden – vervielfältigt, verbreitet und öffentlich zugänglich gemacht werden
- neu zusammengestellt werden – abgewandelt und bearbeitet werden
- Zu den folgenden Bedingungen:
- Namensnennung – Du musst angemessene Urheber- und Rechteangaben machen, einen Link zur Lizenz beifügen und angeben, ob Änderungen vorgenommen wurden. Diese Angaben dürfen in jeder angemessenen Art und Weise gemacht werden, allerdings nicht so, dass der Eindruck entsteht, der Lizenzgeber unterstütze gerade dich oder deine Nutzung besonders.
- Weitergabe unter gleichen Bedingungen – Wenn du das Material wiedermischst, transformierst oder darauf aufbaust, musst du deine Beiträge unter der gleichen oder einer kompatiblen Lizenz wie das Original verbreiten.
Kurzbeschreibungen
Ergänze eine einzeilige Erklärung, was diese Datei darstellt.
In dieser Datei abgebildete Objekte
Motiv
Autor (Text)<\/a>"}},"text\/plain":{"de":{"":"Autor (Text)"}}},"{\"value\":\"Shiyu Ji\",\"type\":\"string\"}":{"text\/html":{"de":{"P2093":"Shiyu Ji","P4174":"Shiyu Ji<\/a>"}},"text\/plain":{"de":{"P2093":"Shiyu Ji","P4174":"Shiyu Ji"}}},"{\"value\":{\"entity-type\":\"property\",\"numeric-id\":4174,\"id\":\"P4174\"},\"type\":\"wikibase-entityid\"}":{"text\/html":{"de":{"":"Wikimedia-Benutzername<\/a>"}},"text\/plain":{"de":{"":"Wikimedia-Benutzername"}}},"{\"value\":{\"entity-type\":\"property\",\"numeric-id\":2699,\"id\":\"P2699\"},\"type\":\"wikibase-entityid\"}":{"text\/html":{"de":{"":"URL<\/a>"}},"text\/plain":{"de":{"":"URL"}}},"{\"value\":\"http:\\\/\\\/commons.wikimedia.org\\\/wiki\\\/User:Shiyu_Ji\",\"type\":\"string\"}":{"text\/html":{"de":{"P2699":"http:\/\/commons.wikimedia.org\/wiki\/User:Shiyu_Ji<\/a>"}},"text\/plain":{"de":{"P2699":"http:\/\/commons.wikimedia.org\/wiki\/User:Shiyu_Ji"}}}}" class="wbmi-entityview-statementsGroup wbmi-entityview-statementsGroup-P170 oo-ui-layout oo-ui-panelLayout oo-ui-panelLayout-framed">
Einige Werte ohne einen Wikidata-Eintrag
urheberrechtlich gesch\u00fctzt<\/a>"}},"text\/plain":{"de":{"P6216":"urheberrechtlich gesch\u00fctzt"}}}}" class="wbmi-entityview-statementsGroup wbmi-entityview-statementsGroup-P6216 oo-ui-layout oo-ui-panelLayout oo-ui-panelLayout-framed">
Creative Commons Namensnennung \u2013 Weitergabe unter gleichen Bedingungen 4.0 International<\/a>"}},"text\/plain":{"de":{"P275":"Creative Commons Namensnennung \u2013 Weitergabe unter gleichen Bedingungen 4.0 International"}}}}" class="wbmi-entityview-statementsGroup wbmi-entityview-statementsGroup-P275 oo-ui-layout oo-ui-panelLayout oo-ui-panelLayout-framed">
28. Dezember 2016
durch Hochlader\/in erstelltes Original<\/a>"}},"text\/plain":{"de":{"P7482":"durch Hochlader\/in erstelltes Original"}}}}" class="wbmi-entityview-statementsGroup wbmi-entityview-statementsGroup-P7482 oo-ui-layout oo-ui-panelLayout oo-ui-panelLayout-framed">
image/gif
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
---|---|---|---|---|---|
aktuell | 14:26, 28. Dez. 2016 | 521 × 518 (5,94 MB) | Shiyu Ji | User created page with UploadWizard |
Dateiverwendung
Die folgende Seite verwendet diese Datei:
Globale Dateiverwendung
Die nachfolgenden anderen Wikis verwenden diese Datei:
- Verwendung auf en.wikipedia.org
- Verwendung auf ko.wikipedia.org
- Verwendung auf no.wikipedia.org
Abgerufen von „https://de.wikipedia.org/wiki/Datei:DijkstraDemo.gif“