پرش به محتوا

پرونده:SPFADemo.gif

Page contents not supported in other languages.
از ویکی‌پدیا، دانشنامهٔ آزاد

SPFADemo.gif(۵۲۱ × ۵۱۸ پیکسل، اندازهٔ پرونده: ۶٫۴۷ مگابایت، نوع MIME پرونده: image/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)

اجازه‌نامه

من، صاحب حقوق قانونی این اثر، به این وسیله این اثر را تحث اجازه‌نامهٔ ذیل منتشر می‌کنم:
w:fa:کرییتیو کامنز
انتساب انتشار مشابه
این پرونده تحت پروانهٔ Creative Commons Attribution-Share Alike 4.0 International منتشر شده است.
شما اجازه دارید:
  • برای به اشتراک گذاشتن – برای کپی، توزیع و انتقال اثر
  • تلفیق کردن – برای انطباق اثر
تحت شرایط زیر:
  • انتساب – شما باید اعتبار مربوطه را به دست آورید، پیوندی به مجوز ارائه دهید و نشان دهید که آیا تغییرات ایجاد شده‌اند یا خیر. شما ممکن است این کار را به هر روش منطقی انجام دهید، اما نه به هر شیوه‌ای که پیشنهاد می‌کند که مجوزدهنده از شما یا استفاده‌تان حمایت کند.
  • انتشار مشابه – اگر این اثر را تلفیق یا تبدیل می‌کنید، یا بر پایه‌ آن اثری دیگر خلق می‌کنید، می‌‌بایست مشارکت‌های خود را تحت مجوز یکسان یا مشابه با ا اصل آن توزیع کنید.

عنوان

شرحی یک‌خطی از محتوای این فایل اضافه کنید

آیتم‌هایی که در این پرونده نمایش داده شده‌اند

توصیف‌ها

این خصوصیت مقداری دارد اما نامشخص است.

source of file انگلیسی

تاریخچهٔ پرونده

روی تاریخ/زمان‌ها کلیک کنید تا نسخهٔ مربوط به آن هنگام را ببینید.

تاریخ/زمانبندانگشتیابعادکاربرتوضیح
کنونی‏۲۸ دسامبر ۲۰۱۶، ساعت ۱۳:۲۲تصویر بندانگشتی از نسخهٔ مورخ ‏۲۸ دسامبر ۲۰۱۶، ساعت ۱۳:۲۲۵۲۱ در ۵۱۸ (۶٫۴۷ مگابایت)Shiyu JiUser created page with UploadWizard

صفحهٔ زیر از این تصویر استفاده می‌کند:

کاربرد سراسری پرونده

ویکی‌های دیگر زیر از این پرونده استفاده می‌کنند: