Datei:SPFADemo.gif
Seiteninhalte werden in anderen Sprachen nicht unterstützt.
Erscheinungsbild
SPFADemo.gif (521 × 518 Pixel, Dateigröße: 6,47 MB, MIME-Typ: image/gif, Endlosschleife, 139 Bilder, 1 min 10 s)
Diese Datei und die Informationen unter dem roten Trennstrich werden aus dem zentralen Medienarchiv Wikimedia Commons eingebunden.
Beschreibung
BeschreibungSPFADemo.gif |
English: A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering. Blue lines are where relaxing happens. |
Datum | |
Quelle | Eigenes Werk |
Urheber | Shiyu Ji |
Python 3 Code
'''
Shortest path covering (SVG) using SP Faster algorithm with 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 spfa(n, points, edges):
nframe = 0
dist = [float("inf") for i in range(n)]
prev = [-1 for _ in range(n)]
cover = []
dist[0] = 0.0
Q = [0]
while len(Q)>0:
u = Q[0]
Q.pop(0)
if prev[u]!=-1:
cover.append([points[prev[u]], points[u]])
saveToSVG(nframe, points, edges, cover, [])
nframe+=1
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
if i not in set(Q): Q.append(i)
for k in range(len(cover)):
if cover[k][1] == points[i]:
cover.pop(k)
break
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)
spfa(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
Einige Werte ohne einen Wikidata-Eintrag
28. Dezember 2016
Dateiversionen
Klicke auf einen Zeitpunkt, um diese Version zu laden.
Version vom | Vorschaubild | Maße | Benutzer | Kommentar | |
---|---|---|---|---|---|
aktuell | 15:22, 28. Dez. 2016 | ![]() | 521 × 518 (6,47 MB) | Shiyu Ji | User created page with UploadWizard |
Dateiverwendung
Keine Seiten verwenden diese Datei.
Globale Dateiverwendung
Die nachfolgenden anderen Wikis verwenden diese Datei:
- Verwendung auf fa.wikipedia.org
- Verwendung auf hu.wikipedia.org
- Verwendung auf zh.wikipedia.org
Abgerufen von „https://de.wikipedia.org/wiki/Datei:SPFADemo.gif“