Ugrás a tartalomhoz

Fájl:SPFADemo.gif

Az oldal más nyelven nem érhető el.
A Wikipédiából, a szabad enciklopédiából

SPFADemo.gif(521 × 518 képpont, fájlméret: 6,47 MB, MIME-típus: image/gif, ismétlődik, 139 képkocka, 1 min 10 s)

Összefoglaló

Leírás
English: A demo of Dijkstra's algorithm based on Euclidean distance. Red lines are the shortest path covering. Blue lines are where relaxing happens.
Dátum
Forrás A feltöltő saját munkája
Szerző 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)

Licenc

Én, e mű szerzője a művemet az alábbi licenc alatt teszem közzé:
w:hu:Creative Commons
Nevezd meg! Így add tovább!
Ez a fájl a Creative Commons Nevezd meg! – Így add tovább! 4.0 Nemzetközi licenc alapján használható fel.
A következőket teheted a művel:
  • megoszthatod – szabadon másolhatod, terjesztheted, bemutathatod és előadhatod a művet
  • feldolgozhatod – származékos műveket hozhatsz létre
Az alábbi feltételekkel:
  • Nevezd meg! – A szerzőt megfelelően fel kell tüntetned, hivatkozást kell létrehoznod a licencre és jelezned kell, ha a művön változtatást hajtottál végre. Ezt bármilyen észszerű módon megteheted, kivéve oly módon, ami azt sugallná hogy a jogosult támogat téged vagy a felhasználásod körülményeit.
  • Így add tovább! – Ha megváltoztatod, átalakítod, feldolgozod ezt a művet, a közreműködésedet csak az eredetivel megegyező vagy hasonló licenc alatt terjesztheted.

Képaláírások

Adj meg egy egysoros magyarázatot arról, hogy mit mutat be ez a fájl

A fájl által ábrázolt elemek

mű tárgya

28. december 2016

Fájltörténet

Kattints egy időpontra, hogy a fájl akkori állapotát láthasd.

Dátum/időBélyegképFelbontásFeltöltőMegjegyzés
aktuális2016. december 28., 15:22Bélyegkép a 2016. december 28., 15:22-kori változatról521 × 518 (6,47 MB)Shiyu JiUser created page with UploadWizard

Az alábbi lap használja ezt a fájlt:

Globális fájlhasználat

A következő wikik használják ezt a fájlt: