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.
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I think you need to provide more detail for us to understand the question. $\endgroup$– 6005May 14 '20 at 12:30
Add a comment
|
$\begingroup$
$\endgroup$
4
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.
-
$\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$ 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$ 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$ 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$ May 6 '20 at 14:21