Suppose we have a weighted graph. by the code implemented here, We can print the shortest path in the graph but what if we have more than one shortest path?
I thought that the nodes can have multiple parents instead of one parent and then for printing them if the node had more than one parent we copy the paths in the size of the node's parent and do the rest as it is, but I don't know if this works or not and how to modify the code mentioned in the link to work like this.
Any help would be appreciated.
Basically the current implementation serves the purpose of a single smallest path and discards any possible ties. In order to make sure that all parents are being processed, change your condition from the strict
if edge_distance > 0 and shortest_distance + edge_distance < shortest_distances[vertex_index]:
to the not-strict
if edge_distance > 0 and shortest_distance + edge_distance <= shortest_distances[vertex_index]:
But you will need to be careful, because here you will have two cases:
In this case you will need to create a new collection and fill it with the single element that's closer than all earlier elements and assign this 1-element collection to the parents graph.
In this case you should already have a collection of parents of the node and you should append the current one there
You should thoroughly test your solution, it's quite possible that you will stumble into recursion problems while you apply the solution, but the basic idea you need to use as your starting point is that, when a given shortest path of D is found from a node to the other, then you will need a collection of that element and whenever you find equally short paths, you just append their representative data to your collection.
Okay. So, I changed the code to allow multiple parents. I create an empty array for the parents of each elements and whenever I find a shorter path, I recreate the parent array for that element and each time when I find a path that's not longer than any previous path, then I add it to the array, so ties end up being inside the array.
For the sake of simplicity, I used a graph of the form of
0 -> 1
| |
v v
2 -> 3
Where all vertices are of a length of 1 and there is a tie from 0 to 3, as 0 -> 1 -> 3 has a path length of 2, the same as for 0 -> 2 > 3.
const NO_PARENT = -1;
function dijkstra(adjacencyMatrix, startVertex) {
const nVertices = adjacencyMatrix[0].length;
// shortestDistances[i] will hold the shortest distance from startVertex to i
const shortestDistances = new Array(nVertices).fill(Number.MAX_SAFE_INTEGER);
// added[i] will true if vertex i is included in shortest path tree
// or shortest distance from startVertex to i is finalized
const added = new Array(nVertices).fill(false);
// Initialize all distances as infinite and added[] as false
for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
shortestDistances[vertexIndex] = Number.MAX_SAFE_INTEGER;
added[vertexIndex] = false;
}
// Distance of source vertex from itself is always 0
shortestDistances[startVertex] = 0;
// Parent array to store shortest path tree
const parents = new Array(nVertices).fill([]);
// The starting vertex does not have a parent
parents[startVertex] = [];
// Find shortest path for all vertices
for (let i = 1; i < nVertices; i++) {
// Pick the minimum distance vertex from the set of vertices not yet processed.
// nearestVertex is always equal to startVertex in first iteration.
let nearestVertex = -1;
let shortestDistance = Number.MAX_SAFE_INTEGER;
for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
if (!added[vertexIndex] && shortestDistances[vertexIndex] < shortestDistance) {
nearestVertex = vertexIndex;
shortestDistance = shortestDistances[vertexIndex];
}
}
// Mark the picked vertex as processed
added[nearestVertex] = true;
// Update dist value of the adjacent vertices of the picked vertex.
for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
const edgeDistance = adjacencyMatrix[nearestVertex][vertexIndex];
if (edgeDistance > 0 && shortestDistance + edgeDistance <= shortestDistances[vertexIndex]) {
if (shortestDistance + edgeDistance < shortestDistances[vertexIndex]) parents[vertexIndex] = [];
if ((parents[vertexIndex].indexOf(nearestVertex) < 0) && (adjacencyMatrix[nearestVertex][vertexIndex] > 0)) parents[vertexIndex].push(nearestVertex);
shortestDistances[vertexIndex] = shortestDistance + edgeDistance;
}
}
}
printSolution(startVertex, shortestDistances, parents);
}
// A utility function to print the constructed distances array and shortest paths
function printSolution(startVertex, distances, parents) {
const nVertices = distances.length;
document.write("Vertex<pre> Distance<pre>Path");
for (let vertexIndex = 0; vertexIndex < nVertices; vertexIndex++) {
if (vertexIndex !== startVertex) {
document.write(`<br>${startVertex} -> ${vertexIndex}\t\t ${distances[vertexIndex]}<pre><pre>`);
let results = printPath(vertexIndex, parents);
for (let r of results) document.write(r + "<br>");
}
}
}
// Function to print shortest path from source to currentVertex using parents array
function printPath(currentVertex, parents, text = "") {
if (currentVertex === 3) debugger;
let results = [];
if (text === "") text = currentVertex;
else text = currentVertex + " -> " + text;
for (let p of parents[currentVertex]) {
let innerResults = printPath(p, parents, text);
for (let ir of innerResults) results.push(ir);
}
if (results.length === 0) results = [text];
return results;
}
// Driver code
const adjacencyMatrix = /*[ [0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]*/
[
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0]
];
dijkstra(adjacencyMatrix, 0);