Member 14538694 Ответов: 1

Как реализовать алгоритм Дейкстры в Python

я хочу реализовать этот псевдокод Дейкстры точно в моем графике python.

Dijkstra's Algorithm DIJKSTRA(G,s,d)  //graph, source, destination   
v ← s //v is always our currently scanned node
    for all n in G.vertices 
       n.tw ← ∞    s.tw ← 0  //Source is no distance from itself
    visited ← []
    while v≠d
         for all vertices, u, adjacent to v
            if v.tw+v[u].w < u.tw
                u.tw ← v.tw+v[u].w
                u.pre ← v         //Store the return path
        visited.append(v)
        min ← ∞        
     for all nodes n ∈ V 
           if n ∉ visited ∧ n.tw < min
                v ← n
                min ← n.tw


Что я уже пробовал:

graph = {

'a':{'b':3,'c':4, 'd':7},
'b':{'c':1,'f':5},
'c':{'f':6,'d':2},
'd':{'e':3, 'g':6},
'e':{'g':3, 'h':4},
'f':{'e':1, 'h':8},
'g':{'h':2},
'h':{'g':2}
}


def dijkstra(graph,start,goal):

1 Ответов

Рейтинг:
2

OriginalGriff

Мы более чем готовы помочь тем, кто застрял, но это не значит, что мы здесь, чтобы сделать все это для вас! Мы не можем сделать всю работу, вам либо платят за это, либо это часть ваших оценок, и было бы совсем несправедливо, если бы мы сделали все это за вас.

Поэтому нам нужно, чтобы вы сделали работу, и мы поможем вам, когда вы застряли. Это не значит, что мы дадим вам пошаговое решение, которое вы можете сдать!
Начните с объяснения, где вы находитесь в данный момент и каков следующий шаг в этом процессе. Затем расскажите нам, что вы пытались сделать, чтобы этот следующий шаг сработал, и что произошло, когда вы это сделали.