Sep-11-2020, 04:29 PM
Given this code, answer the following questions:
a) What does this code do and what does it return?
b) Given that this algorithm can change the weights of some edges, is it possible that the distances that have been calculated before with the function all_pairs_dijkstra_path_length to change when function_x() exits?
For the first question, I think that this code "secures" the triangle inequality by putting a max limit (variable d) for the weights. If I am not mistaken this code will return the number of times that triangle inequality was violated in the graph (variable count).
As for the second question I have literally no clue!
What do you think of these questions?
P.S: 1) This is my first post and I am a beginner programmer.
2) Sorry for my bad english.
import networkx as nx def function_x(G) distances = nx.all_pairs_dijkstra_path_length(G, weight='weight') count = 0 for u, ud in distances: for v, d in ud.items(): if G.has_edge(u, v): if G.edges[u, v]['weight'] > d: count += 1 G.edges[u, v]['weight'] = d return countObviously G stands for a graph with positive weights.
a) What does this code do and what does it return?
b) Given that this algorithm can change the weights of some edges, is it possible that the distances that have been calculated before with the function all_pairs_dijkstra_path_length to change when function_x() exits?
For the first question, I think that this code "secures" the triangle inequality by putting a max limit (variable d) for the weights. If I am not mistaken this code will return the number of times that triangle inequality was violated in the graph (variable count).
As for the second question I have literally no clue!
What do you think of these questions?
P.S: 1) This is my first post and I am a beginner programmer.
2) Sorry for my bad english.