Priority Queue is initialized at line 10 and then same data again “heappushed” in line 15. Is that really required? Can we not start with an empty PriorityQueue? like simply: queue = [ ]
which part are you referring to?
"Therefore, our final time complexity is O(nlog(e)) as maintaining the edges in the queue takes logarithmic time. "
The time complexity for Dijkstra’s algorithm that uses min-priority queue is ((|V|+|E|)log |V|)(where |V| is the number of nodes and |E| is the number of edges) (see the wiki). The queue will only maintain nodes not edges.
Instead of adding all vertices to the priority queue at the beginning, we can add new vertices as we checking the neighbours.
Is adding all vertices to the priority queue at the beginning useful for any situation? I feel just add root at the beginning is always better
The javascript part is incomplete I think, so far I’ve only seen
function shortestPath(graph, a, b) {
// WRITE YOUR BRILLIANT CODE HERE
return 0;
}
function* main() {
const res = shortestPath();
console.log(res);
}
class EOFError extends Error {}
{
const gen = main();
const next = (line) => gen.next(line).done && process.exit();
let buf = ‘’;
next();
process.stdin.setEncoding(‘utf8’);
process.stdin.on(‘data’, (data) => {
const lines = (buf + data).split(‘\n’);
buf = lines.pop();
lines.forEach(next);
});
process.stdin.on(‘end’, () => {
buf && next(buf);
gen.throw(new EOFError());
});
}
at the beginning. Not sure how the graph, a, b value are coming from.
Please include illustrations for all approaches mentioned in the article. Also if possible a git diff between BFS and SPFA to focus on the key differences
can anyone tell me what each element of the graph represents? i’m lost there. what does each list and tuple represent?
each tuple in a sublist is a neighbor of a node (given by its index) - first element of the tuple is the neighbor and 2nd is its weight in relation to the node
in what cases would you get bfs(a, b) == float(‘inf’)?
Yeah I have the same question. On line 10 you do queue = [(0, root)], but then you heappush (0, i) only if i == root on line 15. Commenting out line 15 or initializing queue as an empty list yields passes all tests.
Thanks!!
We can check our priority queue and if the distance in our priority queue is greater than the distance that is currrently in the array we pop it out and skip to the next iteration of the loop.
What does this line mean?
In the Dijkstra’s Algorithm Optimization, what’s the point of pushing nodes with infinite distance into the heap in the first place? If we were to pop from it and hit
if distance > distances[node]
then we ignore it anyway because it was already updated. If it wasn’t updated yet, then we’d loop through it’s neighbors and do nothing since we’d be comparing distances to infinity
d = distances[node] + weight
if distances[neighbor] <= d:
[…]
Nvm I guess that got answered in UCS
For the SPFA, providing the data structure for the graph with a clear example would be nice (for c++ examples). Solution is harder to parse when it’s not clear which part of the structure is the node, which part represents the edges and which part the weight.
For c++ spfa:
Node is the index of outer vector. Values in the outer vector are vectors of edge-weights.
For the pairs, first item is the neighborNodeId, and second item is the weight of the edge.
can somebody add comments in the python code. I need a better explanation of how the code is wxactly working.
In python snippets we have
return -1 if bfs(a, b) == float('inf') else bfs(a, b)
which executes bfs two times for normal cases, instead it should be executed once, result should be saved to a variable and then whether to return -1 should be deduced based on that variable