Question: Given Dijkstras Algorithm (python code) explain on how set1 & set2 work in this Dijkstra function n=3 dis=[[0,1,65535],[1,0,2],[65535,2,0]] #expect result: [0, 1, 3] v=0 def
Given Dijkstras Algorithm (python code) explain on how set1 & set2 work in this Dijkstra function
n=3 dis=[[0,1,65535],[1,0,2],[65535,2,0]] #expect result: [0, 1, 3]
v=0 def Dijkstra(m,n,v): ''' m:matrix<-dis n:the number of nodes v:source node ''' global D D=[m[v][i] for i in range(n)] D[v]=0 set1=set({}) set2=set([i for i in range(n)]) set1.add(v) set2.remove(v) while len(set1)<>n: mini=min([D[i] for i in set2]) for i in set2: if D[i]==mini: x=i break set2.remove(x) set1.add(x) D[x]=mini for i in set2: D[i]=min(D[i],D[x]+m[x][I]) print(D)
Dijkstra(dis,n,v)
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
