Please provide a working code in Python, and NOT pseudocode. Dijkstra\'s shortes

Question

Please provide a working code in Python, and NOT pseudocode.

Dijkstra's shortest path algorithm should be implemented in Python using the following pseudocode. for all u in V: dist(u) = Infinity prev(u) = nil dist(s) = 0 A = makequeue(V) (using dist-values as keys) while A is not empty: u = deletemin(A) for all edges (u; v) 2 E: if dist(v) > dist(u) + I(u; v): dist(v) = dist(u) + I(u; v) prev(v) = u decreasekey(A; v) You may use the HeapDict priority queue implementation that works like a dictionary, and also allows for both insert and decrease key operations by simply setting the dictionary key to a given value. popitem can be used for delete min. The code should take as input a graph with weights, and a starting vertex v, and it should output the shortest path length from v to all vertices in the graph, and you should also output the short path as a list of vertices, such as by using the prev pointers in the pseudocode. The input graph will be shown as a pair of edges and weights. For example: An input that looks like the following: 124 142 232 243 253 421 434 455 531 Means that the edge (5, 3) has the weight of 1. The output appears as: 1: 0, [1] 2: 3, [1, 4, 2] 3: 5, [1, 4, 2, 3] 4: 2, [1, 4] 5: 6, [1, 4, 2, 5] The output is shown as distance from v

Explanation / Answer

class Graph: def __init__(self): self.nodes = set() self.edges = defaultdict(list) self.distances = {} def add_node(self, value): self.nodes.add(value) def add_edge(self, from_node, to_node, distance): self.edges[from_node].append(to_node) self.edges[to_node].append(from_node) self.distances[(from_node, to_node)] = distance def dijsktra(graph, initial): visited = {initial: 0} path = {} nodes = set(graph.nodes) while nodes: min_node = None for node in nodes: if node in visited: if min_node is None: min_node = node elif visited[node]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.