Question

I understand this question is a bit similar to another one asked on this forum, but my question is a specific and the other question did not provide an answer to it.

The algorithm i will be referencing is below. I understand that this algorithm loops through each vertex in a graph and assigns it a value of infinity. It also assigns "s" which is in set V to 0. I am guessing "s" is the parent node? Then it creates a set "A" to store visited nodes. While the set doesn't contain all the vertexes in set "V", it picks a node with the minimum value not already in "A". Then it loops through all the vertexes adj. to this node. It compares the value each adj. node to (value of main node + edge value). Then it sets the adj. node to the value of main node + edge if the value of the adj. node is less than it. My question is, why are we doing this? What is the purpose?

Algorithm (G, s) 
for v in V:
val[v] = infinity
val[s]= 0
A = {} # A is a set
while A != V:
select vertex x not in A with minimum val[x]
A = A /in {x}
for each vertex y adjacent to x:
if (val[x] + w(x, y)) less than val[y]:
val[y] = val[x] + w(x, y)
Was it helpful?

Solution

Here is a small graph:

enter image description here

Choose a as the starting vertex s, run your algorithm by hand, and tell us the contents of the val array. If you still have questions after you do that, then we will be happy to help you.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top