0
$\begingroup$

For Dijkstra’s,i can find shortest paths from source to all vertices in the given graph but how can i calling the algorithm |V| times taking each vertex as a source and store all tables ??? For example : What is the shortest path from 1 to 4? You need to print the value and the exact path vertices starting from 1 and ending at 4.

$\endgroup$
1
  • $\begingroup$ I think you need to provide more detail for us to understand the question. $\endgroup$ – 6005 May 14 '20 at 12:30
1
$\begingroup$

I am assuming here that you want to calculate the all-pairs shortest paths for a graph using Dijkstra's.

First, to find the shortest path between all pairs of vertices, you can create a $ |V|^2 $ matrix where row and column i and j corresponds to the shortest distance from vertex i to vertex j.

Second, to mark the all-path shortest paths' path, you simply set the parent property of each vertex j to the current vertex i you are visiting from every time you have to relax the edge going to j from i. Keeping one set of vertices and edge will be sufficient as an APSP will also produce a tree, similar to a SSSP tree.

$\endgroup$
4
  • $\begingroup$ thank u ,, but how can i applied this using Dijkstra algorithm ? ... this algorithm take Array and the source vertex as a parameter .. so how can i store this in 2D array ? :) $\endgroup$ – Programmer May 4 '20 at 22:07
  • $\begingroup$ Can you be more specific regarding what is the array it takes in. Does it take in the adjacency list or an array of estimates to be updated? $\endgroup$ – Wu Peirong May 5 '20 at 6:01
  • $\begingroup$ it takes adjacency matrix ... so i wanna to store it in 2D array where i's takes the source vertices in each time and j's takes the value of the shortest path between i,j node ... are u understand what i mean ?? $\endgroup$ – Programmer May 5 '20 at 12:43
  • $\begingroup$ You can have 2 functions - the first is the actual Dijkstra algorithm which takes in the adjacency matrix and a source vertex i and run Dijkstra for all shortest paths from i. The second will be the driver which simply calls the first Dijkstra function on every node in the adjacency matrix. $\endgroup$ – Wu Peirong May 6 '20 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.