[ECE592] Project 2 Dijkstra search

import pandas as pd
import numpy as np
import time
import matplotlib.pyplot as plt

# function to find city with smallest distance
def minUnvisited(dist, done, number_of_cities):
    minDistance = float('inf')
    ans = -1
    i = 0
    while(i<number_of_cities):
        if(dist[i] <= minDistance and i not in done):
            minDistance = dist[i]
            ans = i
        i += 1;
    return ans

# function to print path
def printPath(dst, dist, parent, cities):
    if(parent[dst] == -1):
        print(cities[dst])
        return
    printPath(parent[dst], dist, parent, cities)
    print(cities[dst])

# read excel to create matrix of distances
NC = pd.read_excel('NC.xlsx', sheet_name='Miles', index_col=0, index_row=0)
cities = NC.index.values
NC = NC.to_numpy()
number_of_cities = cities.shape[0]

# disallow direct routes for near by cities
i = 0
while(i<number_of_cities):
    j = 0
    while(j<number_of_cities):
        if(i == j):
            NC[i][j] = 0
        if(NC[i][j] > 40):
            NC[i][j] = float('inf')
        j += 1
    i += 1

# Dijkstra search algorithm
dist = [float('inf')] * number_of_cities
parent = [-1] * number_of_cities
src_city = np.where(cities == 'Murphy')[0][0]
dst_city = np.where(cities == 'Elizabeth City')[0][0]
dist[src_city] = 0
done = []
start_time = time.time()
node_traversed = [0]
time_taken = [0]
done_nodes_count = 0
while(len(done) != number_of_cities):
    current = minUnvisited(dist, done, number_of_cities)
    done.insert(0, current)
    if(current == dst_city):
        break
    j = 0
    while(j < number_of_cities):
        if(NC[current][j] != float('inf') and j not in done):
            if(dist[current] + NC[current][j] < dist[j]):
                dist[j] = dist[current] + NC[current][j]
                parent[j] = current
        j += 1;
    done_nodes_count += 1
    node_traversed.append(done_nodes_count)
    time_taken.append(time.time() - start_time)

# print and display results
printPath(dst_city, dist, parent, cities)
print('Distance = ' + str(dist[dst_city]))
print("Runtime = %s seconds" % (time.time() - start_time))
plt.ylabel('Number of nodes traversed')
plt.xlabel('Time in seconds')
plt.plot(time_taken, node_traversed)
plt.show()