/sci/ - Science & Math » Thread #11164703

56KiB, 590x397, Problem.png

View Same Google iqdb SauceNAO

How does Dijkstra work?

Anonymous Thu 21 Nov 01:08:50 2019 No.11164703 View Reply Original Report

Quoted By: >>11164715 >>11164718 >>11164904 >>11164921

How do I get to nodes which haven't been visited yet, but I can't get to without going through visited nodes?
>In node Y
>T has already been visited
>htf do I visit Z?

Anonymous

View Same Google iqdb SauceNAO Description.png, 15KiB, 901x285

Anonymous Thu 21 Nov 2019 01:10:58 No.11164715 Report

Quoted By:

>>11164703
Here's the diagram which I have rn. How would I go about changing R{} and V{}?

Anonymous

Anonymous Thu 21 Nov 2019 01:12:50 No.11164718 Report

Quoted By: >>11164726

>>11164703
If T has already been visited, then the next iteration will take you from T to Z, regardless of where Y takes you

Anonymous

Anonymous Thu 21 Nov 2019 01:17:11 No.11164726 Report

Quoted By: >>11164776

>>11164718
I thought Dijkstra can only take you to a node adjacent to the current node.

Anonymous

Anonymous Thu 21 Nov 2019 01:47:12 No.11164776 Report

Quoted By:

>>11164726
it checks the entire layer of the graph at once not one node at a time

Anonymous

Anonymous Thu 21 Nov 2019 02:47:02 No.11164904 Report

Quoted By:

>>11164703
Dijkstra's algorithm does not act like a "snake" (moving through edges one by one).

It acts more like a network. There is no "current node", there is only the "current set of visited nodes." And then all outgoing edges are evaluated to generate the new shortest distance.

I don't really know how to answer your question directly because there's no way for Y and T to be the only visited nodes in the graph. If your source is node Y, then X will be the first node added to visited nodes. If your source node is T, then S will be the first node added.

Anonymous

Anonymous Thu 21 Nov 2019 02:52:33 No.11164921 Report

Quoted By:

>>11164703
Because it's a shortest path algorithm not a Hamilton circuit, you brainlet cs major

>>>/g/tfo

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches