Nice, although this chapter is somewhat redundant with the previous one. Also, I think optimizations should be included in the code implementation by default or at least in another code implementation example.
If the graph is infinite, how would we initialize the distances map?
If the node does not exists in the distances map, we treat its distance as infinity.
I have been seeing the problems can be solved using Priority Queue. But in C# I don’t have Priority Queue. Please suggest how to approach for this. Thanks.
Could you please update target framework version to V6.0. So that I can use Priority Queue’s.
Thanks
The condition below should be removed!
if node == target:
return distance
there could be a better path that leads to shortest distance; and therefore, until we have explored all paths, we should not return the distance.
Thank you. We will consider .net 6.0
Please double check the starting code for C++, the shortest_path function takes in no parameters!
#include // cout
int shortest_path() {
// WRITE YOUR BRILLIANT CODE HERE
return 0;
}
int main() {
int res = shortest_path();
std::cout << res << ‘\n’;
}
I’m confused, in previous lesson, I’ve found that it’s not required to push all ‘inf’ weights to the queue at the beginning, the I simplified the implementation to this, it still passes all tests
queue = [(0, root)]
distances = []
distances = [float('inf')] * len(graph)
distances[root] = 0
heappush(queue, (0, i))
while len(queue) > 0:
_, node = heappop(queue)
for neighbor, weight in get_neighbors(node):
d = distances[node] + weight
if distances[neighbor] <= d:
continue
heappush(queue, (d, neighbor))
distances[neighbor] = d
return distances[target]
Now the question is, what’s the difference between above implementation and the one for Uniform Cost Search, could anyone explain please?
The above implementation stops when it finds the target. Your implementation doesn’t stop until it finishes calculating the distances for all the nodes in the graph, which could take a really long time if the graph was large.