-
Notifications
You must be signed in to change notification settings - Fork 1
Bellman Ford shortest path visualization.
Bellman ford's algorithm is a single source shortest path algorithm that works on a weighted graph and has the capability of handling negative weights. It is also useful for finding negative weights in a graph. Initially, the cost from the source to all other nodes is set to infinity except for the source which is 0. The algorithm works by calculating the shortest distance from starting vertex to all other vertices this step runs |V| - 1 time and with each iteration, the algorithm will try to explore different routes to reach other nodes. If the algorithm detects a smaller distance, the previously noted costs are relaxed with the newer smaller value. Relaxation is whereby more accurate values are that is, For the edge (u, v), if distance[u]+weight(u, v) < distance[v], update distance[v] = distance[u] + weight(u, v) In practical cases relaxation happens |V| - 1 time, in this visualization we relax edges not more than 10 times because of the size of the graph, although there is a variation of bellman ford's algorithm that relaxes edges on the condition the values keep changing otherwise relaxation stops. Finally, the algorithm will check if there exists a negative cycle, that is after the shortest path is found and relaxation produces an even shorter path, this is a sign of a negative cycle.
Path: /code/assets/js/visual/PathFindingAlgorithms/bellmanFord.js.
From the DOM we get the grid, speed slider button value which we use for timing the speed with which the algorithm will run, and start and clear buttons which we use for starting and clearing the path after running the algorithm. We then initialize count to 1, which times the highlighting of the shortest path throughout all iterations and path count which we use for timing the enabling of the disabled buttons after visualizing the algorithm. We declare the number of times we shall relax nodes of the grid to obtain the shortest path.
Code.
const speedSlider = document.querySelector(".speedSlider");
let time = speedSlider.value;
let count = 1;
let pathCount = 1;
export const relaxations = 5;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).
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;
//5.
let 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.
let prow = parseInt(curr.getAttribute("row"));
let pcol = parseInt(curr.getAttribute("col"));
if (!visited.includes(node)) {
checker.push(node);
bellmanSteps.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 node row, column, parent row, and parent column to the bellmanSteps array which we shall later 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 the first relaxation the node cost would be smaller with an exception of the source node. In all other relaxations, the node cost will be updated and the comparison will be between the two values. 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).
//1.
relax = (x1 = 0, y1 = 0, x2 = rowSize - 1, y2 = colSize - 1) => {
//2.
let startNode = document.querySelector(`div[row='${x1}'][col='${y1}']`);
//3.
let visited = [startNode];
let checker = [startNode];
//4.
while (checker.length != 0) {
//5.
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;
});
//6.
let curr = checker.pop();
//7.
let row = parseInt(curr.getAttribute("row"));
let col = parseInt(curr.getAttribute("col"));
//8.
let wall = parseInt(curr.getAttribute("wall"));
if (wall == 1) continue;
//9.
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);
//10.
count++;
//11.
pathCount++;
}
};- The algorithm takes the first node and last node of the graph.
- We initialize the source node which we use to estimate the shortest path from it to all other nodes.
- 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 the front node from the queue from the checker queue and exploration will continue to its adjacent nodes.
- 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 which we use for the timely highlighting of the path from source to destination nodes.
- We increment the path count which we use to enable the start and clear path buttons after the final shortest path is highlighted.
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.
drawPath = () => {
//1.
let startNode = document.querySelector(
`div[row='${startRow}'][col='${startCol}']`
);
let endNode = document.querySelector(
`div[row='${endRow}'][col='${endCol}']`
);
//2.
setTimeout(() => {
startNode.setAttribute("class", "pathNode");
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}"]`
);
//3.
bellmanFordPath.push([parseInt(prow), parseInt(pcol)]);
}
endNode.setAttribute("class", "pathNode");
}, 1000 * time + 100);
};- We get the source and destination nodes from DOM.
- 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 push nodes that form the shortest path from source to destination to the path array for bellman ford.
The function takes the first and last nodes as parameters and relaxes the nodes 6 times to estimate the accurate shortest paths from the source node to all other nodes in the graph. We relax 6 times because of the size of the graph.
//1.
bellmanFord = (
x1 = 0,
y1 = 0,
x2 = rowSize - 1,
y2 = colSize - 1
) => {
//2.
time = speedSlider.value;
time = 40 + (time - 1) * -2;
//3.
gridContainer.removeEventListener("mousedown", setWall);
gridContainer.removeEventListener("mouseover", setWall);
//4.
let startBtn = document.querySelector(".start");
let clearPathBtn = document.querySelector(".clearPath");
startBtn.setAttribute("disabled", "true");
clearPathBtn.setAttribute("disabled", "true");
//5.
let i = 0;
//6.
let run = () => {
//7.
setInterval(() => {
if (i < relaxations) {
relax(
(x1 = 0),
(y1 = 0),
(x2 = rowSize - 1),
(y2 = colSize - 1)
);
//8.
bellmanStepsLength = bellmanSteps.length;
//9.
i++;
} else {
//9.
setTimeout(() => {
startBtn.removeAttribute("disabled");
clearPathBtn.removeAttribute("disabled");
manualStart.removeAttribute("disabled");
wallBtn.removeAttribute("disabled");
}, pathCount * time + 100);
//10.
clearInterval(run);
}
//11.
drawPath();
}, 5000);
};
//12.
run();
};- The algorithm takes the first and last nodes in the graph.
- Initialize time which we shall use to time the visualization whose value is from the speed slider value from the DOM.
- Remove event listeners to avoid creating walls after the algorithm has already started running.
- Disable the start and clear path buttons to avoid clicking when the algorithm is currently running.
- Initialize relaxations to 1.
- Function to implement the relaxation function 6 times to find the shortest path from the source to all other nodes in the graph.
- Relax the path 6 times in 5-second intervals.
- Store an original length of the array that we use for logging steps, that is, after the first visualization, the following traversals will act as relaxation steps.
- Increment relaxations to clear the interval after 6 relaxations.
- Enable to disabled clear and start buttons.
- Clear the interval timer to avoid infinite loops.
- Draw the shortest path from the source to the destination node.
- Finally we run the function.