Kashish Dugar

My throat hurt today, but I wrote Dijkstra’s algorithm in code!

Tables instead of tags

Yesterday my price tags got messy and I used an old number by mistake. Today I used a table instead, with four columns: Place, Cost, Came from, and Ticked. When a cost changed, I crossed out the old number. The rule is: always use the newest number.

I did two new maps on my own, and both were right.

My table is my code

Every column of my table turned into code:

• Cost became a dictionary called costs
• Came from became a dictionary called parents
• Ticked became a list called ticked

The map is a dictionary of dictionaries. graph["B"]["D"] is the price of the road from B to D.

The sum sentence from yesterday (“₹__ to reach , plus ₹ for the road”) became one line of code:

Bugs I fixed

• My first run never stopped. place never changed, so the loop went on forever, just like Rumi and Neelu asking each other. I had to add place = find_cheapest() inside the loop.
• I predicted 5, but it printed 8. I was thinking of a different map! The code was right.
• The route came out backwards because I walked from Finish to Start. route.reverse() fixed it.

It works

On my big map it printed 8 and the route Start → A → B → D → Finish.

graph = {"Start" : {"A":2, "B":5, "C":4},
        "A" : {"B":1, "D":7},
        "B" : {"D":3, "E":6},
        "C" : {"B":2, "E":4},
        "D" : {"E":1, "Finish":2},
        "E" : {"Finish":3},
        "Finish" : {}}

costs = {"Start" : 0,
        "A" : float("inf"),
        "B" : float("inf"),
        "C" : float("inf"),
        "D" : float("inf"),
        "E" : float("inf"),
        "Finish" : float("inf")}

parents = {"Start" : None,
        "A" : None,
        "B" : None,
        "C" : None,
        "D" : None,
        "E" : None,
        "Finish" : None}

ticked = []

def find_cheapest():
    cheapest = None
    lowest = float("inf")
    for node in costs:
        if node not in ticked and costs[node] < lowest:
            lowest = costs[node]
            cheapest = node
    return cheapest

place = find_cheapest()
while place is not None:
    for neighbour in graph[place]:
        new_cost = costs[place] + graph[place][neighbour] 
        if new_cost < costs[neighbour]:
            costs[neighbour] = new_cost
            parents[neighbour] = place
    ticked.append(place)
    place = find_cheapest()

step = "Finish"
route = []
while step is not None:
    route.append(step)
    step = parents[step]

route.reverse()
print(route)

What’s next

Test my Dijkstra on yesterday’s map. It should print 5 without changing the algorithm.