Алгоритм кратчайшего пути: алгоритм коррекции метки

Question

Я пытаюсь создать программу для алгоритма кратчайшего пути.

То, что я сделал, Читаю файл первенствовать в питоне добавить создание словаря выглядеть следующим образом:

{1: {2: 6, 3: 4}, 2: {1: 6, 6: 5}, 3: {1: 4, 4: 4, 12: 4}, 4: {11: 6, 3: 4, 5: 2}, 5: {9: 5, 4: 2, 6: 4}, 6: {8: 2, 2: 5, 5: 4}, 7: {8: 3, 18: 2}, 8: {16: 5, 9: 10, 6: 2, 7: 3}, 9: {8: 10, 10: 3, 5: 5}, 10: {16: 4, 9: 3, 11: 5, 17: 8, 15: 6}, 11: {12: 6, 10: 5, 4: 6, 14: 4}, 12: {11: 6, 3: 4, 13: 3}, 13: {24: 4, 12: 3}, 14: {23: 4, 11: 4, 15: 5}, 15: {10: 6, 19: 3, 22: 3, 14: 5}, 16: {8: 5, 17: 2, 10: 4, 18: 3}, 17: {16: 2, 10: 8, 19: 2}, 18: {16: 3, 20: 4, 7: 2}, 19: {17: 2, 20: 4, 15: 3}, 20: {18: 4, 19: 4, 21: 6, 22: 5}, 21: {24: 3, 20: 6, 22: 2}, 22: {23: 4, 20: 5, 21: 2, 15: 3}, 23: {24: 2, 22: 4, 14: 4}, 24: {23: 2, 13: 4, 21: 3}} 

Таким образом, каждый узел соединяется с некоторыми другими узлами, имеющих время в пути, связанное с ним ,

Итак, я начал с создания программы путем определения узлов и предшественников узлов. Просматривая цикл, моя метка узла обновляется, если моя предыдущая метка узла + текущее время в пути меньше, чем текущая метка узла. Я также обновляю предшественника, если обновляю это время в пути.

import xlrd # import xlrd python package to play with excel files 

file_location = "C:/Users/12/Desktop/SiouxFalls_net1.xlsx" #defining excel file location 

workbook = xlrd.open_workbook(file_location) #assigning workbook 

sheet = workbook.sheet_by_index(0) #assigning sheet of that workbook 
graph = {} #initializing dictionary for graph 

# as dataset includes a header file then skip the first step by setting rows!=0 
for rows in range(sheet.nrows): #This will read no. of rows 
    if(rows != 0): 
     a = int(sheet.cell_value(rows, 0)) 
     b = int(sheet.cell_value(rows, 1)) 
     c = int(sheet.cell_value(rows, 4)) 
#etdefault() creates a new entry (empty dictionary in this case) only if there is no such entry associated with the 
     # given key. Then it returns the entry (either the newly created empty or the existing one), 
     # so we add into the entry (which is nested dictionary) the new relation. 
     graph.setdefault(a, {})[b] = c 
     graph.setdefault(b, {})[a] = c 
# Reading Nodes 
nodes = [] 
label = {} 
for rows in range(sheet.nrows): 


    if(rows != 0): 
     x = int(sheet.cell_value(rows, 0)) 
     if x not in nodes: #to get unique values from the column 
      nodes.append(x) 


start_node = int(input('Enter the origin')) 
end_node = int(input('Enter the destination')) 
SEL = [start_node] 

pred = {start_node: 0 
     } 
for i in nodes: 
    if(i == start_node): 
     label[i] = 0 
    else: 
     label[i] = 100000000 


for a in SEL: 
    print(a) 
    SEL.remove(a) 
    print(SEL) 
    for b, c in graph[a].items(): 
     print('checking' + str(b)) 
     if (label[b] > label[a] + c): 
      label[b] = label[a] + c 
      pred[b] = a 
      SEL.append(b) 
      print(SEL) 

Так я удаляю SEL каждый раз, чтобы проверить этикетки и предшественника, и добавить узел SEL, если что-то обновляется. Итак, в конце мой SEL должен быть пустым, но мой цикл for останавливается произвольно посередине без завершения списка SEL. Я не знаю почему? Он

Я могу показать вам один пример: я даю начальный узел 15 и конечный узел 5 в качестве адресата, и просто чтобы проверить, что я печатаю все в цикле. Это результат:

Enter the origin15 
Enter the destination5 
15 
[] 
checking10 
[10] 
checking19 
[10, 19] 
checking22 
[10, 19, 22] 
checking14 
[10, 19, 22, 14] 
19 
[10, 22, 14] 
checking17 
[10, 22, 14, 17] 
checking20 
[10, 22, 14, 17, 20] 
checking15 
14 
[10, 22, 17, 20] 
checking23 
[10, 22, 17, 20, 23] 
checking11 
[10, 22, 17, 20, 23, 11] 
checking15 
20 
[10, 22, 17, 23, 11] 
checking18 
[10, 22, 17, 23, 11, 18] 
checking19 
checking21 
[10, 22, 17, 23, 11, 18, 21] 
checking22 
11 
[10, 22, 17, 23, 18, 21] 
checking12 
[10, 22, 17, 23, 18, 21, 12] 
checking10 
checking4 
[10, 22, 17, 23, 18, 21, 12, 4] 
checking14 
21 
[10, 22, 17, 23, 18, 12, 4] 
checking24 
[10, 22, 17, 23, 18, 12, 4, 24] 
checking20 
checking22 
4 
[10, 22, 17, 23, 18, 12, 24] 
checking11 
checking3 
[10, 22, 17, 23, 18, 12, 24, 3] 
checking5 
[10, 22, 17, 23, 18, 12, 24, 3, 5] 
3 
[10, 22, 17, 23, 18, 12, 24, 5] 
checking1 
[10, 22, 17, 23, 18, 12, 24, 5, 1] 
checking4 
checking12 
1 
[10, 22, 17, 23, 18, 12, 24, 5] 
checking2 
[10, 22, 17, 23, 18, 12, 24, 5, 2] 
checking3 
Process finished with exit code 0 

Я хочу, чтобы цикл for продолжался до тех пор, пока мой SEL не будет пустым. Пожалуйста, помогите

Answer 1

Вы должны изменить свой цикл, чтобы что-то вроде этого:

while SEL: 
    a = SEL.pop(0) # removes the first element in SEL and assigns it to a 
    print(a) 
    print(SEL) 
    for b, c in graph[a].items(): 
     print('checking' + str(b)) 
     if (label[b] > label[a] + c): 
      label[b] = label[a] + c 
      pred[b] = a 
      SEL.append(b) 
      print(SEL) 

Вы добавления SEL внутри цикла в коде. Это изменение не подбирается внутри for a in SEL. Вот почему ваша петля заканчивается раньше.