At 1:03, shouldn't the path to B have a distance of -2?
@AlgorithmswithAttitude7 жыл бұрын
Only if you know basic arithmetic. Which, apparently, I do not.
@ashutoshkushwaha53263 жыл бұрын
This video really makes the concepts crystal clear
@MCBPZ6 жыл бұрын
great content! I love the enthusiasm!
@jTay1115 жыл бұрын
shouldn't the x in O(|V|+x*|E|) be the number of levels in the shortest path tree with the greatest height since it's an upper bound?
@jTay1115 жыл бұрын
great content by the way
@AlgorithmswithAttitude5 жыл бұрын
After |V| levels, you will have all vertices in the graph, so for sure it is O(|V|). Of course, it is also O(x) for any x > |V|, but that is not as useful as the smaller bound.
@celstone4 жыл бұрын
Great video as always! Which shortest-path algorithm(s) do you recommend for undirected graphs that contain negative edges and fail via Dijkstra (see your Dijkstra video) or even contain negative-weight cycles (you mention it here: kzbin.info/www/bejne/bXyqoJt5ecqdZ9Um41s )?
@AlgorithmswithAttitude4 жыл бұрын
Wow, I probably should have clarified that. Watching what I said, I had to think about it myself... If the graph is undirected, any negative edge reachable from the source vertex gives you a negative infinite path to everything connected to the source vertex, by just going to that negative edge, traversing it as much as you want, and then moving on. So, in an undirected graph, we could run Dijkstra, and if we run into any negative edge at all, just do DFS from your source, everything reachable gets negative infinity. Sorry it took so long for me to answer, I don't get too many specific content questions like this one. With the link to the specific time, it makes answering it fairly painless. This is how I envisioned answering questions when I put the videos up, and yours is a nice one.