What are the first 3 steps of the given alogrithm. ?This means: visit and expand

Question

What are the first 3 steps of the given alogrithm.
?This means: visit and expand the first 3 nodes starting at 0.
Use the graph above. “0” is the source and “6” is the goal.

(10 Points) Consider the following algorithm to find the shortest distance between two cities (s->G 1. 1.1 3.97 3.1 4.6 Source 0 4.8 2 5.2 6.0 Step 1: Maintain a list of cities C that you have 7 so far Cache the total path-cost g(c) and the proecessor city p(c) for every city c in C Step 2: Maintain a list of neighboring cities F (the fringe) that are not in C. Cn F-Ø Cache the total path-cost g(f) and the predecessor city p(f) for every city f in F Cities in F are ordered according to their total path cost g(f) Step 3: At every iteration of the algorithm, starting at S, visit the city in the fringe that has the lowest path-cost. Add it to C and remove it from F Step 4: Add all new neighboring cities (including their g(f) and p(f)) into the fringe that are not already in C. (It is possible to have copies in F with different predecessors) Step 5: If more than 1 copy of a city is in the fringe, only retain the one with lowest g(f) Delete all other copies. Step 6: IF you reach G, reconstruct the path from S-> G and report g(G) and the path.

Explanation / Answer

The First three steps of algorithm are as follows:

Step 1 :

Right now, you have not visited any city.

So, you are at Source city i.e 0.

Total path cost is 0.

Also, predecessor city is NULL.

Given, C i.e the cities visited so far is also NULL.

Now, Coming to step 2.

Step 2 :

It says that you have to find all the neighbouring cities and make a list in F that are not in C. Since C is empty, So the neighbouring cities that has to be inserted in F are '1' & '2'.

Now, F will have ('1','2'). C will be NULL. Predecessor city P(f) will be ('0','0'). Total Path cost is 0.

Step 3 :

Now, From S i.e '0', we have to visit every city in F i.e ('1','2') and find out the lowest path.

Here, lowest path is 1.1 i.e from '0' city to '1' city.

Then, we have to remove it from F and add it to C.

Now, F will be ('2'). C will be ('1'). Total Path cost will be g(f) will be 1.1

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.