پرونده:SPFADemo.gif
SPFADemo.gif (۵۲۱ × ۵۱۸ پیکسل، اندازهٔ پرونده: ۶٫۴۷ مگابایت، نوع MIME پرونده: image/gif، چرخشدار، ۱۳۹ قاب، ۱ دقیقه ۱۰ ثانیه)
این پرونده در ویکیانبار موجود است. محتویات صفحهٔ توصیف آن در زیر نمایش داده میشود. |
خلاصه
توضیحSPFADemo.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. |
تاریخ | |
منبع | اثر شخصی |
پدیدآور | 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)
اجازهنامه
من، صاحب حقوق قانونی این اثر، به این وسیله این اثر را تحث اجازهنامهٔ ذیل منتشر میکنم:
این پرونده تحت پروانهٔ Creative Commons Attribution-Share Alike 4.0 International منتشر شده است.
- شما اجازه دارید:
- برای به اشتراک گذاشتن – برای کپی، توزیع و انتقال اثر
- تلفیق کردن – برای انطباق اثر
- تحت شرایط زیر:
- انتساب – شما باید اعتبار مربوطه را به دست آورید، پیوندی به مجوز ارائه دهید و نشان دهید که آیا تغییرات ایجاد شدهاند یا خیر. شما ممکن است این کار را به هر روش منطقی انجام دهید، اما نه به هر شیوهای که پیشنهاد میکند که مجوزدهنده از شما یا استفادهتان حمایت کند.
- انتشار مشابه – اگر این اثر را تلفیق یا تبدیل میکنید، یا بر پایه آن اثری دیگر خلق میکنید، میبایست مشارکتهای خود را تحت مجوز یکسان یا مشابه با ا اصل آن توزیع کنید.
آیتمهایی که در این پرونده نمایش داده شدهاند
توصیفها
این خصوصیت مقداری دارد اما نامشخص است.
۲۸ دسامبر 2016
source of file انگلیسی
original creation by uploader انگلیسی
تاریخچهٔ پرونده
روی تاریخ/زمانها کلیک کنید تا نسخهٔ مربوط به آن هنگام را ببینید.
تاریخ/زمان | بندانگشتی | ابعاد | کاربر | توضیح | |
---|---|---|---|---|---|
کنونی | ۲۸ دسامبر ۲۰۱۶، ساعت ۱۳:۲۲ | ۵۲۱ در ۵۱۸ (۶٫۴۷ مگابایت) | Shiyu Ji | User created page with UploadWizard |
کاربرد پرونده
صفحهٔ زیر از این تصویر استفاده میکند:
کاربرد سراسری پرونده
ویکیهای دیگر زیر از این پرونده استفاده میکنند:
- کاربرد در hu.wikipedia.org
- کاربرد در zh.wikipedia.org
برگرفته از «https://fa.wikipedia.org/wiki/پرونده:SPFADemo.gif»