Given Dijkstra’s Algorithm (python code) explain on how set1 & set2 work in this

Question

Given Dijkstra’s 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)

Explanation / Answer

According to given Dijkstra’s Algorithm (python code)

set1 contains all visited nodes during calculating minimum distance of all vertices from a given source vertex;
initially, set1 ={} is an empty set because no vertex has visited ,
and as Algorithm progresses, it keeps on adding vertices to set1 until set1 contains total n vertices.

set2 contains all non-visited nodes during calculating minimum distance of all vertices from a given source vertex;
initially, set2 ={[i for i in range(n)]} is set containing all vertices graph has ,because no vertex has visited ;
and as Algorithm progresses,it keeps on removing vertices from set2;

During each iteration if algorithm finds a new vertex with minimum distance in set2
it remove that vertex from set2 and add it to set1 until set1 has total n vertices.

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

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