CoCalc Logo Icon
StoreFeaturesDocsShareSupportNewsAboutSign UpSign In

CoCalc’s goal is to provide the best real-time collaborative environment for Jupyter Notebooks, LaTeX documents, and SageMath, scalable from individual use to large groups and classes.

| Download
Project: MAT 2540
Views: 89
Visibility: Unlisted (only visible to those who know the link)
Image: ubuntu2004
Tweet
Share
Share
Kernel: Python 3 (Anaconda 2021)

Dijkstra's Algorithm

import networkx as nx

g = nx.Graph()

g.add_nodes_from('abcdez')

L =[('a','b',4),('a','c',2),('b','d',5),('c','e',10),('b','c',1),('c','d',8),('d','e',2),('d','z',6),('e','z',3)]

g.add_weighted_edges_from(L)

nx.draw(g,with_labels=True,edges)
File "/tmp/ipykernel_438/3548183082.py", line 1 nx.draw(g,with_labels=True,edges) ^ SyntaxError: positional argument follows keyword argument 
w = 0
for edge in g.edges():
    w += g[edge[0]][edge[1]]['weight']
labels = {'a':0,'b':w,'c':w,'d':w,'e':w,'z':w}
S = []
while 'z' not in S:
    minNode = 'z'
    minWeight = labels['z']
    for node in g.nodes():
        if node not in S and labels[node] < minWeight:
            minNode = node
            minWeight = labels[node]
    S.append(minNode)
    print(labels)
    for v in labels.keys():
        if v not in S and g.has_edge(minNode,v):
            labels[v] = min(labels[v],labels[minNode]+g[minNode][v]['weight'])
labels['z']
{'a': 0, 'b': 41, 'c': 41, 'd': 41, 'e': 41, 'z': 41} {'a': 0, 'b': 4, 'c': 2, 'd': 41, 'e': 41, 'z': 41} {'a': 0, 'b': 3, 'c': 2, 'd': 10, 'e': 12, 'z': 41} {'a': 0, 'b': 3, 'c': 2, 'd': 8, 'e': 12, 'z': 41} {'a': 0, 'b': 3, 'c': 2, 'd': 8, 'e': 10, 'z': 14} {'a': 0, 'b': 3, 'c': 2, 'd': 8, 'e': 10, 'z': 13}
13
nx.dijkstra_path_length(g,'a','z')
13