My attempt at Dijkstra's Algorithm in Python 3

I am practicing my coding at HackerRank. The exact problem statement can be found here, but to summarize, it is finding the distances of the shortest path from a starting node to every other node in a non-directional graph where every edge is weighted 6. If a node is unreachable, the distance is -1. The nodes are named 1 to n. If you want an example, please see the provided one in the link.

To solve this, I googled an explanation of Dijkstra's Algorithm and tried my best to implement it (I am new to graph problems). My program passes 6/7 of the test cases, but it times out on the 7th. I improved some small inefficiencies, but it wasn't enough. Please advise me on how I may make the following faster:

```
def shortest (start, nodes, adj):
unique = [] #this part is pretty standard for this Algorithm I think
distance = [float('inf')]*nodes
for i in range(1, nodes+1):
if (len(adj[i-1])>0):
unique.append(i)
distance [start-1] = 0
while (len(unique)>0):
minDist = float('inf')
for i in unique:
if (distance[i-1] <= minDist):
minDist = distance[i-1]
distIndex = i
current = distIndex #sets the current node as the closest unvisited node
unique.remove(current)
for i in adj[current-1]: #updates the distance of each neighbour of the current node
neigh = i
temp = 6 + distance[current-1] #edges are 6
if temp < distance[neigh-1]:
distance[neigh-1] = temp
return distance

q = int(input()) #each test case contains multiple problems, so just consider one iteration

for i in range(q):
a = [] #for input purposes
b = [] #for output purposes
node = 0
edge = 0

#start of input
node, edge = list(map(int, input().strip().split())) #the input begins with the number of nodes and edges in the graph
for j in range(edge):
a.append(list(map(int, input().strip().spl

Those comments are very difficult to read.

j = list(set(j)) #someone warned that the problematic test case gives the same edge many times, so this is to remove duplicates

Format this properly:

# The problematic test case gives the same edge many times,
# so this is to remove duplicates
j = list(set(j))

Then remove fluff:

# Remove duplicates. Helps some test cases.
j = list(set(j))

In this case just remove the first comment, because list(set(...)) is already known to mean deduplicate. And remove the second since it's implied by the fact you've written the code.

j = list(set(j))

Another pair is

a = [] # for input purposes
b = [] # for output purposes

Don't do this. Just call them

descriptive_name_1 = []
descriptive_name_2 = []

so you don't need the comment in the first place.

Then there's q = .... So I wrack my brain thinking about what word contains q. But it turns out you just meant to write num_test_cases. What does that have to do with the letter q?

Worse than that is when you outright lie. What would you expect the variable node to contain? A node, right? Nope - it contains the total number of nodes.

And you write

node = 0

so we expect the total number of nodes to be 0 at that point, right? Nope, you immediately change your mind and write

node, edge = list(map(int, input().strip().split()))

But OK, fine. At least we know what nodes contains, then: multiple nodes, so a list (or other collection) of lengths of nodes.

Nope, it actually means exactly the same thing as node.

A similar comment goes for edge, which should be num_edges.

Then there's adj, which you label "adjacency matrix". Why not just call it adjacency_matrix then? But it's not even a dense matrix like that would imply, it's actually a list of per-node adjacencies, so call it adjacencies.

Then there's starting and start, which are the same thing named differently. Call them start_node or at least be consistent.

Going back to b, you have

b = []

but again this is a lie, because actually

b = shortest(start_node, num_nodes, adjacencies)

So just write that.

distances = shortest(start_node, num_nodes, adjacencies)

For a, initialize it as close to usage as possible and call it edges.

If you write

for j in range(num_edges):

you're misleading me into thinking you're going to use the index. When you're not going to, write

for _ in range(num_edges):

And what's up with that, followed by

for j in edges:

followed by

for j in adjacencies:

Is j just your general "this is a thing" variable? Most people use x, elem and item for that. Instead, write

for _ in range(num_edges):
for edge in edges:
for adjacent in adjacencies:

The middle can be

for start, end in edges:

The comment

#edges are 6

Isn't coherent. Try

# Edges are length 6

Instead, though, don't put this information in shortest - use 1 and multiply out when using the results.

Don't call variables temp. It's a poor name.

You've double-indented the part where you update the neighbours.

Note that

num_nodes, num_edges = list(map(int, input().strip().split()))

is just

num_nodes, num_edges = map(int, input().strip().split())

Why do you do this?

for i in adjacencies[current-1]:
    neigh = i

Just write

for neighbour in adjacencies[current-1]:

And the content can be

for neighbour in adjacencies[current-1]:
    distance[neighbour-1] = min(distance[neighbour-1], distance[current-1] + 1)

Do you not think this whole -1 thing is getting a bit silly? When reading, just decrement the edge values and starting edge correctly:

edges = []
for _ in range(num_edges):
    start, end = map(int, input().strip().split())
    edges.append((start - 1, end - 1))

start_node = int(input()) - 1

while loops and if statements don't need their condition parenthesized, and operators should be spaced properly:

while (len(unique)>0):   # before
while len(unique) > 0:   # after

Then this is better as just while unique.

Don't put spaces before the parentheses in function calls or indexing.

minDist should be min_dist. You can also start with it set to num_nodes, and the same for distance's initialization.

unique is a horrible name, and has nothing to do with the variable's purpose. Try unvisited instead. It can be initialized as

unvisited = [i for i, adj in enumerate(adjacencies) if adj]

distance, unsurprisingly, does not mean distance but instead distances. Fix that.

This code:

min_dist = num_nodes
for i in unvisited:
    if distances[i] <= min_dist:
        min_dist = distances[i]
        distIndex = i
current = distIndex

is just

min_dist = num_nodes
for i in unvisited:
    if distances[i] <= min_dist:
        min_dist = distances[i]
        current = i

and `cur

StackExchange Code Review Q#138989, answer score: 12