-
Notifications
You must be signed in to change notification settings - Fork 1
Dijkstra's shortest path visualization.
Dijkstra's algorithm works on weighted directed or undirected graphs to find the shortest path from the source to all other nodes in the graph. It is only applicable to weighted graphs with positive edges but fails when negative edges are involved. All the nodes' cost is initially set to infinity except the source vertex. The algorithm will start from the source node and will find the shortest path from the source to all other nodes in the graph. We use a visited array to store already visited nodes. This will continue until all nodes have been visited and the shortest path from source to destination is highlighted.
Path: /code/assets/js/visual/PathFindingAlgorithms/bfs.js.
We first get the speed slider button value which we use for timing the speed with which the algorithm will run.
const speedSlider = document.querySelector(".speedSlider");
let time = speedSlider.value;We change the colors of nodes under exploration and nodes already explored layer by layer. The function takes the current node under exploration, count which we use for timing, and cost which we use to label the cost from source to that node, after exploration, a path from the source node to the destination node is highlighted with green color after the fire reaches the destination node. It will change the color of nodes with timing first denoting exploration(green-blue) then followed by the node being selected as a path(green).
const changeColor = (node, count, cost) => {
setTimeout(() => {
node.setAttribute("class", "chosenPath");
if (cost) {
node.innerHTML = cost;
}
}, count * time);
setTimeout(() => {
node.setAttribute("class", "pathColor");
}, count * time + 100);
};It takes the coordinates(row, col) to keep track of the position we are at in the grid, the current node under exploration, a visited array to store visited nodes, and the count which we use for timing. This algorithm is responsible for updating the nodes, that is, it will change the colors and update the cost which is the distance from the source to that node.
//1.
checkUpdateNode = (row, col, curr, checker, visited, count) => {
//2.
if (row >= 0 && col >= 0 && row < rowSize && col < colSize) {
//3.
let node = document.querySelector(`div[row="${row}"][col="${col}"]`);
//4.
let wall = parseInt(node.getAttribute("wall"));
if (wall == 1) return;
let prow = parseInt(curr.getAttribute("row"));
let pcol = parseInt(curr.getAttribute("col"));
//5.
var cost = Math.min(
parseInt(curr.getAttribute("cost")) +
parseInt(node.getAttribute("weight")),
node.getAttribute("cost")
);
//6.
if (cost < node.getAttribute("cost")) {
node.setAttribute(
"parent",
curr.getAttribute("row") + "|" + curr.getAttribute("col")
);
node.setAttribute("cost", cost);
}
//7.
changeColor(curr, count, curr.getAttribute("cost"));
//8.
if (!visited.includes(node)) {
checker.push(node);
bfsSteps.push([row, col, cost, prow, pcol]);
}
//9.
visited.push(node);
//10.
return node;
} else {
//11.
return false;
}
};- The algorithm takes the current row and column, the current node being explored, checker queue and visited array, and count.
- Checking edge cases to ensure traversal does not extend the grid. That is, the algorithm will run as long as the following conditions stand; Row and column coordinates are greater than 0, meaning at least 0. keep in mind that (0,0) is the least coordinate in the grid. Row and column coordinates are not greater than the number of grid rows and columns.
- We get the node that we are currently at during the traversal of the grid.
- We avoid walls, if there is a wall nothing is done, and the function returns.
- Minimize the cost from the current node to the next by comparing the current node cost + next node cost and the cost of the next node which at this point is initialized to Positive Infinity.
- We go incrementing the cost from the source node layer to the current layer, as we do so we keep track of the path by setting parent attribute with coordinates at that point which we shall use to trace the shortest path from the source to destination.
- We change the colors and the cost from the source to that node.
- Check if the node is already explored, if not we explore it and later we push it to the visited array. We also push the row, column, cost at a node, the parent row, and parent column to the bfs steps array which we shall use to explore the algorithm in steps(manually).
- Push the already visited node to the visited array.
- Return visited node.
- Otherwise we return false.
We keep an array visited to store already visited nodes by this time they have a cost which we use to estimate the shortest path from the source. All costs of nodes start as (+)infinity to make sure that in every comparison the node cost would be smaller with an exception of the source node. First, we pick a vertex with the shortest current cost, visit it and add it to the visited array. Then update the costs of all adjacent unvisited neighbors, that is for every node a, b, where b is unvisited if shortestPath(source, b) + shortestPath(a, b) < shortestPath(source, b), we update the shortest path a, b to shortestPath(source, a) + shortestPath(a, b). Here is the code,
//1.
dijkstra = (x1 = 0, y1 = 0, x2 = rowSize - 1, y2 = colSize - 1) => {
//2.
time = speedSlider.value;
time = 40 + (time - 1) * -2;
gridContainer.removeEventListener("mousedown", setWall);
gridContainer.removeEventListener("mouseover", setWall);
let startNode = document.querySelector(`div[row='${x1}'][col='${y1}']`);
let endNode = document.querySelector(`div[row='${x2}'][col='${y2}']`);
//3.
let startBtn = document.querySelector(".start");
let clearPathBtn = document.querySelector(".clearPath");
startBtn.setAttribute("disabled", "true");
clearPathBtn.setAttribute("disabled", "true");
//4.
let visited = [startNode];
let checker = [startNode];
let count = 1;
//5.
while (checker.length != 0) {
//6.
checker.sort((a, b) => {
if (
parseInt(a.getAttribute("cost")) <
parseInt(b.getAttribute("cost"))
)
return 1;
if (
parseInt(a.getAttribute("cost")) >
parseInt(b.getAttribute("cost"))
)
return -1;
return 0;
});
//7.
let curr = checker.pop();
//8.
let row = parseInt(curr.getAttribute("row"));
let col = parseInt(curr.getAttribute("col"));
//9.
let wall = parseInt(curr.getAttribute("wall"));
if (wall == 1) continue;
//10.
checkUpdateNode(row + 1, col, curr, checker, visited, count);
checkUpdateNode(row - 1, col, curr, checker, visited, count);
checkUpdateNode(row, col - 1, curr, checker, visited, count);
checkUpdateNode(row, col + 1, curr, checker, visited, count);
//11.
count++;
}
}- The algorithm takes the first node and last node in the graph.
- Here we initialize time which we use to time the visualization, the source, and destination nodes, we remove event listeners to prevent adding walls after the visualization has already started.
- Disabling the start and clear path buttons to prevent clicking during the execution of the algorithm.
- We initialize the checker queue, visited array for storing already visited nodes, and count which increments after each iteration and later we use it for timing the algorithm.
- Checker array will act as a queue where we store nodes and once we explore a node we pop it from the queue, so while the queue is not empty we perform actions.
- Return 1 if the cost of the element at the front of the queue is less than the incoming element, -1 if the cost is greater otherwise return 0.
- We pop a node from the checker queue and exploration of adjacent nodes will start from this node.
- We get the current position we are at in the graph during traversal.
- We ignore walls/obstacles, in such cases, we return nothing.
- These functions will enable us to traverse the right, left, bottom, and left sides of a node during the traversal.
- We increment count throughout the whole procedure, that is until nodes added to the checker(queue) are all popped(explored). We use this for the timing of the algorithm.
After the algorithm explores all nodes from source to destination, this function will estimate the shortest path from source to destination, and the path is highlighted with green color.
//draw route
setTimeout(() => {
//1.
startNode.setAttribute("class", "pathNode");
//3.
while (endNode.getAttribute("parent") != "null") {
endNode.setAttribute("class", "chosenPath");
let coor = endNode.getAttribute("parent").split("|");
let prow = parseInt(coor[0]);
let pcol = parseInt(coor[1]);
endNode = document.querySelector(
`div[row="${prow}"][col="${pcol}"]`
);
//4.
dijkstrasPath.push([parseInt(prow), parseInt(pcol)]);
}
//5..
endNode = document.querySelector(`div[row="${x2}"][col="${y2}`);
endNode.setAttribute("class", "pathNode");
}, count * time + 100);
//6.
setTimeout(() => {
startBtn.removeAttribute("disabled");
clearPathBtn.removeAttribute("disabled");
manualStart.removeAttribute("disabled");
wallBtn.removeAttribute("disabled");
}, count * time + 100);- We maintain the styling of the start node to denote the source of the path.
- Remember the updating of nodes where we set the values of the parent attribute to the node coordinates, we use this node attribute to trace the shortest path from source to destination highlighted by the color green.
- We maintain the styling of the end node to denote the destination.
- Store nodes on the path from source to destination in an array which we shall use for highlighting the path after traversal.
- We enable the clear path and start button, one can restart the algorithm or add more obstacles and restart the algorithm.
- Enable buttons that were disabled during the visualization.