[ / / / / / / / / / / / / / ] [ dir / random / cloveros / cuteboys / erp / fast / hydrus / in / strek / tftg ]

/g/ - Technology

Make /g/ Great Again
Name
Email
Subject
Comment *
File
Password (Randomized for file and post deletion; you may also set your own.)
Archive
* = required field[▶ Show post options & limits]
Confused? See the FAQ.
Embed
(replaces files and can be used instead)
Voice recorder Show voice recorder

(the Stop button will be clickable 5 seconds after you press Record)
Options
dicesidesmodifier

Allowed file types:jpg, jpeg, gif, png, webm, mp4, swf, pdf
Max filesize is 16 MB.
Max image dimensions are 15000 x 15000.
You may upload 5 per post.


File: a403da29293dc8c⋯.png (7.26 KB, 210x210, 1:1, Dijkstras.png)

 No.8905

I'm having a tough time wrapping my head around this. The way I understand it, I'm building a tree graph where each node's parent is the adjacent node with the smallest number of steps back to the origin. The tree represents a vector field that plots the shortest course back to origin from every node. Yet in this diagram from the wikipedia article some nodes have two parents.

Is this diagram wrong or am I not understanding something?

____________________________
Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

 No.8907

Firstly, I apologise if this is all over the place.

You assign one node as the root, and traverse one of the adjacent nodes from there. If there appears to be a single node only connected to one other, then it's simply marked as visited, and the distance is compared to the others, as usual.

I'm only a student and so all I know is what the exam paper wants me to write, but as far as I know, any node other than your target node can be assigned as the root, even if it seems that there could logically be another.

You assign one node as the root. Pick any neighbouring node, note its distance. If the distance to the root's neighbouring nodes have all been found, mark the root as visited. If not, go to the other neighbour. Graph traversal algorithms are all about the distance; even though a nide might have two parents, it doesn't quite work that way, because that specific node is visited by the previous node with the shortest distance so far. And it isn't about the number of steps, but rather the value of the distance between two nodes.

Again, sorry this is disorganised, but I hope I helped somewhat.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

 No.8912

>>8907

I see what you mean, until a node is visited it's distance isn't finalized. It must be the nodes with more than one edge drawn had a node tentatively set as the shortest neighbor back to start in step 4, but was reassigned in a later iteration.

1 Mark all nodes unvisited and give them a distance of +INF.

2 Pick a root node to start, assigning it a distance of zero

3 Get a list of all the adjacent unvisited nodes of the current node

4 Compute the distance to each of these nodes as current node's distance + edge length. For a square grid like this diagonals are longer than cardinals to avoid zigzagging all over the place. If this distance is smaller than it's tentative current distance, replace it with the newly calculated distance.

5 Mark the current node as visited.

6 Find an unvisited node with the smallest travel distance less than +INF as the current node. If none exists the destination is unreachable, if this node is the destination return the path by recursively retrieving visited neighboring nodes with the lowest distance, otherwise set this as the current node and go to step 3.

If untraversable nodes exist they would be marked as visited at the start so they are never considered, or visited/unvisited status could be represented by presence in visited and unvisited sets and they would be placed in neither.

The parent node isn't necessary. Setting all these parent references would always be more computationally intensive than backtracking by evaluating neighbors on the way back unless the destination was adjacent to the start, the path nodes and their adjacent nodes are small compared to the number of nodes evaluated. A* might use parent node references since the number of nodes evaluated grows along a much narrower front generally toward the goal. I'll try implementing an animated demo like the pic was from tomorrow.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

 No.8953

bump

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

 No.8973

You wouldn't use dijkstra for the example pic though. Probably BFS or A*

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.

 No.9006

>>8973

BFS follows the same approach, if you understand one you know the other.

Disclaimer: this post and the subject matter and contents thereof - text, media, or otherwise - do not necessarily reflect the views of the 8kun administration.



[Return][Go to top][Catalog][Nerve Center][Random][Post a Reply]
Delete Post [ ]
[]
[ / / / / / / / / / / / / / ] [ dir / random / cloveros / cuteboys / erp / fast / hydrus / in / strek / tftg ]