Не могу реализовать мой график короткого пути с использованием Python 3 - PullRequest
Новая
       62

Не могу реализовать мой график короткого пути с использованием Python 3

0 голосов
/ 23 января 2019

Я работаю над простым кодом, который даст мне кратчайший путь в графе с использованием словарей и циклов.

Тем не менее, я немного запутался в процессе и не могу получить правильный ответ.

Я пытался сделать код как можно более простым: у меня есть два словаря - один для посещенных, а другой для не посещенных узлов. 

class Graph:
    def __init__(self):
        self.graph = {
           'A': {'B': 10, 'D': 4, 'F': 10},
           'B': {'E': 5, 'J': 10, 'I': 17},
           'C': {'A': 4, 'D': 10, 'E': 16},
           'D': {'F': 12, 'G': 21},
           'E': {'G': 4},
           'F': {'H': 3},
           'G': {'J': 3},
           'H': {'G': 3, 'J':5},
           'I': {},
           'J': {'I': 8}
        }

    def shortpath(self, start, end):
        D = {} 
        P = {} 

         for knote in self.graph.keys():
            D[knote] = - 1  
            P[knote] = ""  

        D[start] = 0  


        unvisited_n = list(self.graph.keys()) 

        while len(unvisited_n) > 0:

            shortest = None
            knote = ''
            for temp_node in unvisited_n:
                if shortest == None:
                    shortest = D[temp_node]
                    node = temp_node
                elif D[temp_node] < shortest:
                    shortest = D[temp_node]
                    knote = temp_node

                if knote in unvisited_n:
                    unvisited_n.remove(knote)


        for c_knote, v_value in self.graph[knote].items():
            if D[c_knote] < D[knote] + v_value:
                D[c_knote] = D[knote] + v_value

                P[c_knote] = knote

                path = []

                knote = end


        while not (knote == start):
            if path.count(knote) == 0:
                path.insert(0, knote) 
                knote = P[knote]  
            else:
                break
                path.insert(0, start) 
            return path

def main():
    gg = Graph()
    path = gg.shortpath('C', 'I')
    print(path)

if __name__ == '__main__':
    main()

Я ожидаю, что выходной сигнал будет кратчайшим путем между C (начальная точка) и I (конечная точка)…. Я не мог также инициализировать алгоритм. То есть всякий раз, когда я набираю следующую ячейку: «shortpath (graph, 'C', 'I')", я получаю SyntaxError или «Shorpath не был определен» ...

Заранее благодарю за время и терпение!

...