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

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Databases Questions!