3
Contributors
3
Replies
5
Views
5 Years
Discussion Span
Last Post by alwaysLearning0
0

Dijkstra is your man.

Thank u for ur advice but it would be better if u elaborate little better as i went through Dijkstra' Algo and got that it is for weighted graph for least weight path rather than least number of path .

And i made an algo myself by using n*n matrix having complexity O(n^4) and got TLE(time limit exceed).

if u help a more that 'll be kind :)

0

Thank u for ur advice but it would be better if u elaborate little better as i went through Dijkstra' Algo and got that it is for weighted graph for least weight path rather than least number of path .

Dijkstra is a least number path problem, it will give you shortest path for a single source,
But after reading your prblem, so far I understand you need all pair shortest path, which will give you the shortest paths from every source to every destination in O(n^3)

After finding the shortest path, you need to find the average of those path per source, which is another O(n^2) search, then just need to give output of the lowest average one.

Complexity = O(n^3) + O(n^2)
you can ommit O(n^2)
so basically its O(n^3)

Here is the all pair shortest path algo:
all pair shortest path

Your input should create a graph where each existing edge's weight will be 1, and non existing edge will be infinity (MAX_INT)

Best of luck.

Edited by alwaysLearning0: n/a

This article has been dead for over six months. Start a new discussion instead.
Be sure to adhere to our posting rules.