You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
In order to verify, I have used python networkx to find the MST and then calculate the cost.
Using networkx the value of sum of edges of MST is -2355343 as opposed to -2357954 as provided.
The following is the code:
import networkx as nx
from typing import Dict, List, Tuple
def getNxGraph(fname: str):
graph: List[Tuple[str, str, Dict[str, int]]] = []
with open(fname, "r") as f:
for line in f:
if len(line.split()) < 3:
continue
v1, v2, weight = line.split()
weight = int(weight)
temp = (v1, v2, {"weight": weight})
graph.append(temp)
G = nx.Graph()
for g in graph:
e1, e2, wt = g
G.add_edge(e1, e2, weight=wt["weight"])
return G
if __name__ == "__main__":
fname = f"input_random_33_1000.txt"
G = getNxGraph(fname)
G = nx.minimum_spanning_tree(G)
s = sorted(G.edges(data=True))
mincost = sum(
[e[2]["weight"] for e in s]
) # [('1', '2', {'weight': 1}), ('1', '3', {'weight': 4}), ('2', '4', {'weight': 2})]
print(s)
print(f"mincost {mincost}")
The text was updated successfully, but these errors were encountered:
In order to verify, I have used python networkx to find the MST and then calculate the cost.
Using
networkx
the value of sum of edges of MST is -2355343 as opposed to -2357954 as provided.The following is the code:
The text was updated successfully, but these errors were encountered: