Shortest Path Algorithm: Label correcting algorithm
<p>I am trying to make a program for the shortest path algorithm.</p>

<p>What I have done, 
I am reading a excel file in python add creating a dictionary look like this:</p>

<pre><code>{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}}
</code></pre>

<p>So, every node is connected to some other nodes having a travel time associated with it. </p>

<p>So I started by creating a program by defining node lables and node predecessor. 
While going through the loop, my node label updates if my previous node label + current travel time is less than than the current node label. I also update the predecessor if I update this travel time. </p>

<pre><code>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] &gt; label[a] + c):
            label[b] = label[a] + c
            pred[b] = a
            SEL.append(b)
            print(SEL)
</code></pre>

<p>So I remove SEL every time, in order to check labels and predecessor, and add a node to SEL, if something is updated. So, at the end my SEL should be empty, but my for loop stop arbitrarily in the middle without finishing SEL list. I don't know why?he </p>

<p>I can show you one example, I am giving start node 15 and end node 5 as the destination, and just to check out I am printing everything within the loop. This is the output:</p>

<pre><code>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
</code></pre>

<p>I want my for loop to continue until my SEL is empty. Please help</p>

<p>You need to change your for loop to something like this:</p>

<pre><code>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] &gt; label[a] + c):
            label[b] = label[a] + c
            pred[b] = a
            SEL.append(b)
            print(SEL)
</code></pre>

<p>You are appending SEL inside the loop in your code. This change does not get picked up inside <code>for a in SEL</code>. That's the reason why your loop finishes early.</p>

python networking shortest-path