Hey , i am new to data structure and specially Graph .
And i was going through a problem for finding the best path http://www.codechef.com/JULY11/problems/LOKBIL/ And couldn't think something usable.
SO , if u guys help that will be a good start of me on this site too.
PS i know contest is live so all i want is how to start , and little hint for program .
Thanks in Advance !!
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 :)
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.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.