What file do you want to read? graph3.txt Vertices: [san_francisco, miami, boston, las_vegas, denver, dallas, new_york, seattle, los_angeles, minneapolis, chicago, washington_dc] Edges: san_francisco -> seattle: 1306 san_francisco -> los_angeles: 629 san_francisco -> las_vegas: 919 miami -> dallas: 2161 miami -> washington_dc: 1709 miami -> new_york: 2145 boston -> new_york: 338 boston -> chicago: 1613 boston -> washington_dc: 725 las_vegas -> dallas: 1983 las_vegas -> los_angeles: 435 las_vegas -> denver: 1225 las_vegas -> san_francisco: 919 denver -> dallas: 1258 denver -> las_vegas: 1225 denver -> seattle: 2161 denver -> minneapolis: 1483 dallas -> minneapolis: 1532 dallas -> denver: 1258 dallas -> las_vegas: 1983 dallas -> washington_dc: 2113 dallas -> miami: 2161 new_york -> washington_dc: 383 new_york -> boston: 338 new_york -> miami: 2145 seattle -> minneapolis: 2661 seattle -> denver: 2161 seattle -> san_francisco: 1306 los_angeles -> las_vegas: 435 los_angeles -> san_francisco: 629 minneapolis -> chicago: 661 minneapolis -> denver: 1483 minneapolis -> dallas: 1532 minneapolis -> seattle: 2661 chicago -> minneapolis: 661 chicago -> washington_dc: 1145 chicago -> boston: 1613 washington_dc -> dallas: 2113 washington_dc -> miami: 1709 washington_dc -> boston: 725 washington_dc -> new_york: 383 washington_dc -> chicago: 1145 Removing vertex los_angeles from the priority queue and visiting it. Considering edge (u, v) = los_angeles -> san_francisco Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 0 + 629 = 629 Updating dist[san_francisco] from 999999 to 629 (adding/updating san_francisco in the pri queue also). Updating prev[san_francisco] from undefined to los_angeles. Considering edge (u, v) = los_angeles -> las_vegas Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 0 + 435 = 435 Updating dist[las_vegas] from 999999 to 435 (adding/updating las_vegas in the pri queue also). Updating prev[las_vegas] from undefined to los_angeles. Removing vertex las_vegas from the priority queue and visiting it. Considering edge (u, v) = las_vegas -> san_francisco Old distance (dist[v]) = 629 New distance (alt = dist[u] + weight(u, v)) = 435 + 919 = 1354 No update needed; alt is not less than old distance. Considering edge (u, v) = las_vegas -> dallas Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 435 + 1983 = 2418 Updating dist[dallas] from 999999 to 2418 (adding/updating dallas in the pri queue also). Updating prev[dallas] from undefined to las_vegas. Considering edge (u, v) = las_vegas -> denver Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 435 + 1225 = 1660 Updating dist[denver] from 999999 to 1660 (adding/updating denver in the pri queue also). Updating prev[denver] from undefined to las_vegas. Considering edge (u, v) = las_vegas -> los_angeles Old distance (dist[v]) = 0 New distance (alt = dist[u] + weight(u, v)) = 435 + 435 = 870 No update needed; alt is not less than old distance. Removing vertex san_francisco from the priority queue and visiting it. Considering edge (u, v) = san_francisco -> las_vegas Old distance (dist[v]) = 435 New distance (alt = dist[u] + weight(u, v)) = 629 + 919 = 1548 No update needed; alt is not less than old distance. Considering edge (u, v) = san_francisco -> seattle Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 629 + 1306 = 1935 Updating dist[seattle] from 999999 to 1935 (adding/updating seattle in the pri queue also). Updating prev[seattle] from undefined to san_francisco. Considering edge (u, v) = san_francisco -> los_angeles Old distance (dist[v]) = 0 New distance (alt = dist[u] + weight(u, v)) = 629 + 629 = 1258 No update needed; alt is not less than old distance. Removing vertex denver from the priority queue and visiting it. Considering edge (u, v) = denver -> dallas Old distance (dist[v]) = 2418 New distance (alt = dist[u] + weight(u, v)) = 1660 + 1258 = 2918 No update needed; alt is not less than old distance. Considering edge (u, v) = denver -> las_vegas Old distance (dist[v]) = 435 New distance (alt = dist[u] + weight(u, v)) = 1660 + 1225 = 2885 No update needed; alt is not less than old distance. Considering edge (u, v) = denver -> seattle Old distance (dist[v]) = 1935 New distance (alt = dist[u] + weight(u, v)) = 1660 + 2161 = 3821 No update needed; alt is not less than old distance. Considering edge (u, v) = denver -> minneapolis Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 1660 + 1483 = 3143 Updating dist[minneapolis] from 999999 to 3143 (adding/updating minneapolis in the pri queue also). Updating prev[minneapolis] from undefined to denver. Removing vertex seattle from the priority queue and visiting it. Considering edge (u, v) = seattle -> san_francisco Old distance (dist[v]) = 629 New distance (alt = dist[u] + weight(u, v)) = 1935 + 1306 = 3241 No update needed; alt is not less than old distance. Considering edge (u, v) = seattle -> denver Old distance (dist[v]) = 1660 New distance (alt = dist[u] + weight(u, v)) = 1935 + 2161 = 4096 No update needed; alt is not less than old distance. Considering edge (u, v) = seattle -> minneapolis Old distance (dist[v]) = 3143 New distance (alt = dist[u] + weight(u, v)) = 1935 + 2661 = 4596 No update needed; alt is not less than old distance. Removing vertex dallas from the priority queue and visiting it. Considering edge (u, v) = dallas -> miami Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 2418 + 2161 = 4579 Updating dist[miami] from 999999 to 4579 (adding/updating miami in the pri queue also). Updating prev[miami] from undefined to dallas. Considering edge (u, v) = dallas -> denver Old distance (dist[v]) = 1660 New distance (alt = dist[u] + weight(u, v)) = 2418 + 1258 = 3676 No update needed; alt is not less than old distance. Considering edge (u, v) = dallas -> las_vegas Old distance (dist[v]) = 435 New distance (alt = dist[u] + weight(u, v)) = 2418 + 1983 = 4401 No update needed; alt is not less than old distance. Considering edge (u, v) = dallas -> minneapolis Old distance (dist[v]) = 3143 New distance (alt = dist[u] + weight(u, v)) = 2418 + 1532 = 3950 No update needed; alt is not less than old distance. Considering edge (u, v) = dallas -> washington_dc Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 2418 + 2113 = 4531 Updating dist[washington_dc] from 999999 to 4531 (adding/updating washington_dc in the pri queue also). Updating prev[washington_dc] from undefined to dallas. Removing vertex minneapolis from the priority queue and visiting it. Considering edge (u, v) = minneapolis -> denver Old distance (dist[v]) = 1660 New distance (alt = dist[u] + weight(u, v)) = 3143 + 1483 = 4626 No update needed; alt is not less than old distance. Considering edge (u, v) = minneapolis -> dallas Old distance (dist[v]) = 2418 New distance (alt = dist[u] + weight(u, v)) = 3143 + 1532 = 4675 No update needed; alt is not less than old distance. Considering edge (u, v) = minneapolis -> seattle Old distance (dist[v]) = 1935 New distance (alt = dist[u] + weight(u, v)) = 3143 + 2661 = 5804 No update needed; alt is not less than old distance. Considering edge (u, v) = minneapolis -> chicago Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 3143 + 661 = 3804 Updating dist[chicago] from 999999 to 3804 (adding/updating chicago in the pri queue also). Updating prev[chicago] from undefined to minneapolis. Removing vertex chicago from the priority queue and visiting it. Considering edge (u, v) = chicago -> boston Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 3804 + 1613 = 5417 Updating dist[boston] from 999999 to 5417 (adding/updating boston in the pri queue also). Updating prev[boston] from undefined to chicago. Considering edge (u, v) = chicago -> minneapolis Old distance (dist[v]) = 3143 New distance (alt = dist[u] + weight(u, v)) = 3804 + 661 = 4465 No update needed; alt is not less than old distance. Considering edge (u, v) = chicago -> washington_dc Old distance (dist[v]) = 4531 New distance (alt = dist[u] + weight(u, v)) = 3804 + 1145 = 4949 No update needed; alt is not less than old distance. Removing vertex washington_dc from the priority queue and visiting it. Considering edge (u, v) = washington_dc -> miami Old distance (dist[v]) = 4579 New distance (alt = dist[u] + weight(u, v)) = 4531 + 1709 = 6240 No update needed; alt is not less than old distance. Considering edge (u, v) = washington_dc -> boston Old distance (dist[v]) = 5417 New distance (alt = dist[u] + weight(u, v)) = 4531 + 725 = 5256 Updating dist[boston] from 5417 to 5256 (adding/updating boston in the pri queue also). Updating prev[boston] from chicago to washington_dc. Considering edge (u, v) = washington_dc -> dallas Old distance (dist[v]) = 2418 New distance (alt = dist[u] + weight(u, v)) = 4531 + 2113 = 6644 No update needed; alt is not less than old distance. Considering edge (u, v) = washington_dc -> new_york Old distance (dist[v]) = 999999 New distance (alt = dist[u] + weight(u, v)) = 4531 + 383 = 4914 Updating dist[new_york] from 999999 to 4914 (adding/updating new_york in the pri queue also). Updating prev[new_york] from undefined to washington_dc. Considering edge (u, v) = washington_dc -> chicago Old distance (dist[v]) = 3804 New distance (alt = dist[u] + weight(u, v)) = 4531 + 1145 = 5676 No update needed; alt is not less than old distance. Removing vertex miami from the priority queue and visiting it. Considering edge (u, v) = miami -> dallas Old distance (dist[v]) = 2418 New distance (alt = dist[u] + weight(u, v)) = 4579 + 2161 = 6740 No update needed; alt is not less than old distance. Considering edge (u, v) = miami -> new_york Old distance (dist[v]) = 4914 New distance (alt = dist[u] + weight(u, v)) = 4579 + 2145 = 6724 No update needed; alt is not less than old distance. Considering edge (u, v) = miami -> washington_dc Old distance (dist[v]) = 4531 New distance (alt = dist[u] + weight(u, v)) = 4579 + 1709 = 6288 No update needed; alt is not less than old distance. Removing vertex new_york from the priority queue and visiting it. Considering edge (u, v) = new_york -> boston Old distance (dist[v]) = 5256 New distance (alt = dist[u] + weight(u, v)) = 4914 + 338 = 5252 Updating dist[boston] from 5256 to 5252 (adding/updating boston in the pri queue also). Updating prev[boston] from washington_dc to new_york. Considering edge (u, v) = new_york -> miami Old distance (dist[v]) = 4579 New distance (alt = dist[u] + weight(u, v)) = 4914 + 2145 = 7059 No update needed; alt is not less than old distance. Considering edge (u, v) = new_york -> washington_dc Old distance (dist[v]) = 4531 New distance (alt = dist[u] + weight(u, v)) = 4914 + 383 = 5297 No update needed; alt is not less than old distance. Removing vertex boston from the priority queue and visiting it. Shortest path is: los_angeles las_vegas dallas washington_dc new_york boston Distance is: 5252 Final dist map: san_francisco: 629 miami: 4579 boston: 5252 las_vegas: 435 denver: 1660 dallas: 2418 new_york: 4914 seattle: 1935 los_angeles: 0 minneapolis: 3143 chicago: 3804 washington_dc: 4531 Final prev map: san_francisco: los_angeles miami: dallas boston: new_york las_vegas: los_angeles denver: las_vegas dallas: las_vegas new_york: washington_dc seattle: san_francisco los_angeles: undefined minneapolis: denver chicago: minneapolis washington_dc: dallas