Graph And Data Structure

[melfoy]

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 !!

[\007]

Dijkstra is your man.

[melfoy]

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

[alwaysLearning0]

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.