Questions Tagged With shortest-pathhttps://inoi15.discuss.codechef.com/tags/shortest-path/?type=rssquestions tagged <span class="tag">shortest-path</span>enWed, 21 Jan 2015 23:08:45 +0530Can someone solve FREETICKET from INOI 2014?https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014<p>Hi everyone.
I've been practicing on the INOI server lately, however I've not yet solved even a single question. I studied Graph Theory for the first time last week and decided to do the FREETICKET problem using Djikstra's Algorithm (<a href="http://www.iarcs.org.in/inoi/2014/inoi2014/inoi2014-qpaper.pdf">here</a>).</p>
<p>I've tried to solve the problem innumerable times, but am still not able to do so. If someone could please tell me the pseudocode, it'll be of great help. I'm asking for the pseudo code as I program in Java and am sometimes not able to understand c++ syntax. </p>
<p>Also, if you could review my pseudo code once, I'll be very grateful.
<code></code></p><code>
<p>int[] max = new int[vertices]
for each vertex u = 1 -> v:
int[] dist = new int[vertices]
dist[u] = 0
for each int i = 1 -> v:
if i != u:
dist[i] = INFINITY
for each int i = 0 -> v:
if edge exists from u->i:
int tmp = dist[u] + weight[u][i]
if tmp < dist[i]:
dist[i] = tmp
max[u] = maximum(dist)
int f = maximum(max)
return f //here max is an array and maximum is the
//function for finding maximum value</p>
</code><p><code></code></p>
<p>I realize this is a tedious work but please help me, it's really important.</p>
<p>Thank you all for your help, guys.</p>
<p>Note: when I'm trying the sample case, it returns maximum int value, which means the relaxation is not being done properly.</p>pm1511Sun, 04 Jan 2015 00:47:17 +0530https://inoi15.discuss.codechef.com/questions/60652/can-someone-solve-freeticket-from-inoi-2014bfsgraphshortest-pathGraph algorithmshttps://inoi15.discuss.codechef.com/questions/61805/graph-algorithms<p>Hi friends,
Please refer me a good book for learning the basics of Graph Theory.( Such as shortest paths.)</p>anupam_dattaThu, 15 Jan 2015 23:35:56 +0530https://inoi15.discuss.codechef.com/questions/61805/graph-algorithmsshortest-pathShortest path from BFS and DFShttps://inoi15.discuss.codechef.com/questions/62375/shortest-path-from-bfs-and-dfs<p>Hi all,
I recently learnt how to implement breadth-first-search (BFS) using C++ STL vector. However, though I know the algorithm of depth-first-search (DFS) but cannot understand how to implement it using C++ STL. Please provide me a code using C++ STL to implement it.
Also kindly tell me how the shortest path algorithms (such as Dijkstra's algorithm or Floyd-Warshall's algorithm) can be derived from BFS and DFS.</p>
<p>Thanks in advance!</p>anupam_dattaWed, 21 Jan 2015 23:08:45 +0530https://inoi15.discuss.codechef.com/questions/62375/shortest-path-from-bfs-and-dfsbfsdfsshortest-path