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 iterationfor 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().split()))) #reading the edges, which are all inputted next    starting = int(input()) #reading the starting node    #end of input    adj = [[] for x in range(node)] #the adjacency matrix    for j in a: #making the adjacency matrix from the inputted edges        adj[j[0]-1].append(j[1])           adj[j[1]-1].append(j[0])    for j in adj:        j = list(set(j)) #someone warned that the problematic test case gives the same edge many times, so this is to remove duplicates    b = shortest(starting, node, adj)    #formatting the output to what the question required    b.remove(0)    for i in range(len(b)):        if b[i] == float('inf'):            b[i] = -1    print ( .join(str(e) for e in b))If it helps, I 'purchased' the test case which is timing out.
My attempt at Dijkstra's Algorithm in Python 3
python;python 3.x;graph;time limit exceeded
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 duplicatesFormat this properly:# The problematic test case gives the same edge many times,# so this is to remove duplicatesj = 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 isa = [] # for input purposesb = [] # for output purposesDon't do this. Just call themdescriptive_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 writenode = 0so we expect the total number of nodes to be 0 at that point, right? Nope, you immediately change your mind and writenode, 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 haveb = []but again this is a lie, because actuallyb = 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 writefor j in range(num_edges):you're misleading me into thinking you're going to use the index. When you're not going to, writefor _ in range(num_edges):And what's up with that, followed byfor j in edges:followed byfor j in adjacencies:Is j just your general this is a thing variable? Most people use x, elem and item for that. Instead, writefor _ in range(num_edges):for edge in edges:for adjacent in adjacencies:The middle can befor start, end in edges:The comment#edges are 6Isn't coherent. Try# Edges are length 6Instead, 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 thatnum_nodes, num_edges = list(map(int, input().strip().split()))is justnum_nodes, num_edges = map(int, input().strip().split())Why do you do this?for i in adjacencies[current-1]:    neigh = iJust writefor neighbour in adjacencies[current-1]:And the content can befor 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()) - 1while loops and if statements don't need their condition parenthesized, and operators should be spaced properly:while (len(unique)>0):   # beforewhile len(unique) > 0:   # afterThen 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 asunvisited = [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_nodesfor i in unvisited:    if distances[i] <= min_dist:        min_dist = distances[i]        distIndex = icurrent = distIndexis justmin_dist = num_nodesfor i in unvisited:    if distances[i] <= min_dist:        min_dist = distances[i]        current = iand current should be called closest. It is simplifiable toclosest = min(unvisited, key=lambda x: distances[x])This is faster if you writeclosest = min(unvisited, key=distances.__getitem__)but the difference isn't vital.One last thing with shortest - rename it to shortest_distances.Put the rest of the code in a main function.If you writedef read_pair(decrement):    x, _, y = input().partition( )    return int(x) - decrement, int(y) - decrementthen you can initialize num_nodes, num_edges and edges withnum_nodes, num_edges = read_pair(0)edges = [read_pair(1) for i in range(num_edges)]Note my use of partition instead of split as IMO it's a better description of the operation here.Thenfor adjacent in adjacencies:    adjacent = list(set(adjacent))doesn't actually work! adjacent = only affects the local scope! Instead, you wantadjacencies = [list(set(adj)) for adj in adjacencies]which is even better asadjacencies = [set() for _ in range(num_nodes)]for start, end in edges:    adjacencies[start].add(end)    adjacencies[end].add(start)as you never have the large intermediates then, and there's no real point converting back from a set.This stuff:distances.remove(0)for i in range(len(distances)):    if distances[i] == num_nodes:        distances[i] = -1    else:        distances[i] *= 6print( .join(str(e) for e in distances))is justprint(*(-1 if i == num_nodes else i * 6 for i in distances if i))Nice, that seems to have made it fast enough, but more important the code is more readable.We can improve speed further by avoiding input, using sys.stdin directly to get buffering.def main(lines):    def read_pair(decrement):        x, _, y = next(lines).partition( )        return int(x) - decrement, int(y) - decrement    ...main(sys.stdin)Note that this change is sufficient on its own to beat the time limit: you can apply it to your original code to pass the test. Note also that you shouldn't mix input with next; at least on Python 2 this throws an error sayingValueError: Mixing iteration and read methods would lose dataThough this error is gone in Python 3, that doesn't leave me feeling good about it.I'd finish off withfrom __future__ import print_functionto make it Python 2 compatible.from __future__ import print_functionimport sysdef shortest_distances(start_node, num_nodes, adjacencies):    distances = [num_nodes] * num_nodes    unvisited = [i for i, adj in enumerate(adjacencies) if adj]    distances[start_node] = 0    while unvisited:        closest = min(unvisited, key=distances.__getitem__)        unvisited.remove(closest)        # Update the distances of each neighbour        for neighbour in adjacencies[closest]:            distances[neighbour] = min(distances[neighbour], distances[closest] + 1)    return distancesdef main(lines):    def read_pair(decrement):        x, _, y = next(lines).partition( )        return int(x) - decrement, int(y) - decrement    num_test_cases = int(next(lines))    for i in range(num_test_cases):        num_nodes, num_edges = read_pair(0)        edges = [read_pair(1) for i in range(num_edges)]        start_node = int(next(lines)) - 1        adjacencies = [set() for _ in range(num_nodes)]        for start, end in edges:            adjacencies[start].add(end)            adjacencies[end].add(start)        distances = shortest_distances(start_node, num_nodes, adjacencies)        print(*(-1 if i == num_nodes else i * 6 for i in distances if i))main(sys.stdin)