Python – Algorithm – Calculate Average distance with Dijkstra

In the current article I will try to solve a problem for calculation of average distance with Dijkstra, given in codeforces.com contest here in pdf.

What is the problem like?

We have n weighted graphs like this:

For each given graph, we should print the average of all paths in the graph. It is not that trivial, because for the given graph the result looks like this:

(6+3+7+9+9+13+15+10+12+2)/10 = 8.6

E.g. man should consider not only the direct paths, but also the not direct ones and possibly the shortest one if applicable. Thus, having the words “shortest” and “graph” in a task, we go to Dijkstra! 🙂 My solution is not optimal, because I am not using built up classes as stack in order to make it, but it works 🙂

It looks like this:

#Possible input:
#1
#5
#0 1 6
#0 2 3
#0 3 7
#3 4 2

#Output:
#8.6

def visit_position(list_results,list_visited):
    #returns the position in list_results of the smallest value, which is not visited
    list_smallest = []
    smallest_value = float('inf')
    
    for i in range(0,len(list_visited)):       
        if list_results[i] != float('inf') and list_visited[i] == 0:
            list_smallest.append(i)
            
    for i in range(0, len(list_smallest)):
        if list_results[list_smallest[i]]

That is all folks!

Enjoy it in GitHub as well!