After thinking about it for a bit, you realize that you can use a single execution of the BFM algorithm to determine which cities are closer by distance (and the routes to get there) from Sacramento and which are closer to Salt Lake City. To do so, consider the following modification of the algorithm. Instead of just initializing a single start nodes with a cost label v = 0 and pred = -1, you can simply give all start nodes those values. For example: v(SAC) = 0 v (SLC) = 0 Similarly, you should include all start nodes in the initial label update list L: L = [SAC, SLC]. Complete the execution of the BFM algorithm given this modified initialization. You can execute the iterations by hand or modify code to solve this part; if you choose to modify code, please also write down the first 5 iterations by hand where an iteration is defined by removing a node from L and updating its neighbor labels (and predecessors) as needed. Draw your final result by showing which cities are closer to Sacramento and which are closer to Salt Lake City, labeling your network with the distances to the closer distribution center. Road Segment Endpoints Highway(s) Time Distance (Min) (Miles) Yellowstone N.P., WY Livingston, MT US-89 84 59 Yellowstone N.P., WY Idaho Falls, ID US-20 128 100 Livingston, MT Butte, MT I-90 100 104 Butte, MT Idaho Falls, ID I-15 210 205 Butte, MT Missoula, MT I-90 110 119 Missoula, MT Boise, ID US-12, US-95 475 371 Idaho Falls, ID Salt Lake City, UT I-15 206 208 Idaho Falls, ID Boise, ID Boise, ID Twin Falls, ID Salt Lake City, UT Salt Lake City, UT Twin Falls, ID I-15, 1-86, 1-84 155 161 Twin Falls, ID I-84 128 131 Winnemuca, NV US-95 303 256 Wells, NV US-93 141 118 Wells, NV I-80 174 181 Ely, NV I-15, US-6 262 241 Wells, NV Winnemuca, NV I-80 162 175 Wells, NV Ely, NV US-93 180 140 Winnemuca, NV Reno, NV 1-80 153 164 Ely, NV Bishop, CA US-6 337 283 Reno, NV Bishop, CA US-395 255 205 Reno, NV Sacramento, CA 1-80 152 133 Reno, NV Yosemite N.P., CA US-395, CA-120 225 154 Sacramento, CA Bishop, CA Yosemite N.P., CA CA-99, CA-120 277 193 Yosemite N.P., CA US-395, CA-120 132 65 Figure 1: Bi-directional Distance and Travel Time Data

After thinking about it for a bit, you realize that you can use a single execution of the BFM algorithm to determine which cities are closer by distance (and the routes to get there) from Sacramento and which are closer to Salt Lake City. To do so, consider the following modification of the algorithm. Instead of just initializing a single start nodes with a cost label v = 0 and pred = -1, you can simply give all start nodes those values. For example: v(SAC) = 0 v (SLC) = 0 Similarly, you should include all start nodes in the initial label update list L: L = [SAC, SLC]. Complete the execution of the BFM algorithm given this modified initialization. You can execute the iterations by hand or modify code to solve this part; if you choose to modify code, please also write down the first 5 iterations by hand where an iteration is defined by removing a node from L and updating its neighbor labels (and predecessors) as needed. Draw your final result by showing which cities are closer to Sacramento and which are closer to Salt Lake City, labeling your network with the distances to the closer distribution center. Road Segment Endpoints Highway(s) Time Distance (Min) (Miles) Yellowstone N.P., WY Livingston, MT US-89 84 59 Yellowstone N.P., WY Idaho Falls, ID US-20 128 100 Livingston, MT Butte, MT I-90 100 104 Butte, MT Idaho Falls, ID I-15 210 205 Butte, MT Missoula, MT I-90 110 119 Missoula, MT Boise, ID US-12, US-95 475 371 Idaho Falls, ID Salt Lake City, UT I-15 206 208 Idaho Falls, ID Boise, ID Boise, ID Twin Falls, ID Salt Lake City, UT Salt Lake City, UT Twin Falls, ID I-15, 1-86, 1-84 155 161 Twin Falls, ID I-84 128 131 Winnemuca, NV US-95 303 256 Wells, NV US-93 141 118 Wells, NV I-80 174 181 Ely, NV I-15, US-6 262 241 Wells, NV Winnemuca, NV I-80 162 175 Wells, NV Ely, NV US-93 180 140 Winnemuca, NV Reno, NV 1-80 153 164 Ely, NV Bishop, CA US-6 337 283 Reno, NV Bishop, CA US-395 255 205 Reno, NV Sacramento, CA 1-80 152 133 Reno, NV Yosemite N.P., CA US-395, CA-120 225 154 Sacramento, CA Bishop, CA Yosemite N.P., CA CA-99, CA-120 277 193 Yosemite N.P., CA US-395, CA-120 132 65 Figure 1: Bi-directional Distance and Travel Time Data

Enhanced Discovering Computers 2017 (Shelly Cashman Series) (MindTap Course List)

1st Edition

ISBN:9781305657458

Author:Misty E. Vermaat, Susan L. Sebok, Steven M. Freund, Mark Frydenberg, Jennifer T. Campbell

Publisher:Misty E. Vermaat, Susan L. Sebok, Steven M. Freund, Mark Frydenberg, Jennifer T. Campbell

Chapter8: Digital Storage : Preserving Content Locally And On The Cloud

Section: Chapter Questions

Problem 25CT

See similar textbooks

Related questions

Question

In this problem, we will consider problems of finding minimum cost paths in directed networks. You are performing logistics analysis for a company that distributes products from several distribution centers located around the US. You are considering adding a new distribution center to serve key cities in the Great Basin area. Currently, you operate single distribution center in Sacramento and serve all of the Great Basin cities from there. You are considering opening a new DC in Salt Lake City to improve service and reduce outbound transportation costs from the DC. See the map at the end of this assignment. Currently, your customers are located in all of the major and mid-sized cities represented by blue circles on the map. You have compiled data on the major highway routes that your truck fleet will use when traveling between your key customer areas and your distribution centers. Figure 1 summarizes the data. You have decided to collect both travel time and travel distance data. Travel distance will influence the costs of your truck transportation while travel time will allow you to understand you quickly you can deliver customer orders.

Question:

We would like to compare the travel distances from the current DC in Sacramento with those from the new potential DC in Salt Lake City to each other. For this problem, please use the Bellman-Ford-Moore DP Algorithm.

After thinking about it for a bit, you realize that you can use a single execution of the
BFM algorithm to determine which cities are closer by distance (and the routes to get there)
from Sacramento and which are closer to Salt Lake City.
To do so, consider the following modification of the algorithm. Instead of just initializing
a single start nodes with a cost label v = 0 and pred = -1, you can simply give all start
nodes those values. For example:
v(SAC) = 0
v (SLC) = 0
Similarly, you should include all start nodes in the initial label update list L: L = [SAC, SLC].
Complete the execution of the BFM algorithm given this modified initialization. You can
execute the iterations by hand or modify code to solve this part; if you choose to modify
code, please also write down the first 5 iterations by hand where an iteration is defined by
removing a node from L and updating its neighbor labels (and predecessors) as needed.
Draw your final result by showing which cities are closer to Sacramento and which are
closer to Salt Lake City, labeling your network with the distances to the closer distribution
center.

Road Segment Endpoints
Highway(s)
Time Distance
(Min)
(Miles)
Yellowstone N.P., WY
Livingston, MT
US-89
84
59
Yellowstone N.P., WY
Idaho Falls, ID
US-20
128
100
Livingston, MT
Butte, MT
I-90
100
104
Butte, MT
Idaho Falls, ID
I-15
210
205
Butte, MT
Missoula, MT
I-90
110
119
Missoula, MT
Boise, ID
US-12, US-95
475
371
Idaho Falls, ID
Salt Lake City, UT
I-15
206
208
Idaho Falls, ID
Boise, ID
Boise, ID
Twin Falls, ID
Salt Lake City, UT
Salt Lake City, UT
Twin Falls, ID
I-15, 1-86, 1-84
155
161
Twin Falls, ID
I-84
128
131
Winnemuca, NV
US-95
303
256
Wells, NV
US-93
141
118
Wells, NV
I-80
174
181
Ely, NV
I-15, US-6
262
241
Wells, NV
Winnemuca, NV
I-80
162
175
Wells, NV
Ely, NV
US-93
180
140
Winnemuca, NV
Reno, NV
1-80
153
164
Ely, NV
Bishop, CA
US-6
337
283
Reno, NV
Bishop, CA
US-395
255
205
Reno, NV
Sacramento, CA
1-80
152
133
Reno, NV
Yosemite N.P., CA
US-395, CA-120
225
154
Sacramento, CA
Bishop, CA
Yosemite N.P., CA
CA-99, CA-120
277
193
Yosemite N.P., CA
US-395, CA-120 132
65
Figure 1: Bi-directional Distance and Travel Time Data

Expert Solution

Step by step

Solved in 2 steps with 2 images

SEE SOLUTION Check out a sample Q&A here