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 contest here in pdf.

What is the problem like?

We have n weighted graphs like this:

code_forcesFor 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:

That is all folks!

Enjoy it in GitHub as well!

Tagged with: , ,