Question

Write a python code to generate a random undirected weighted graph and calculate the shortest distance from node i to node j (shortest path algorithm) where i is not equal to j. Store the results in text file. Thank you!

Answer 1

Python Code:

import random as rand

#We will use floyd warshall algorithm to find shortest path from any i to j

def floydWarshall(graph):
  spg=[]
  v=len(graph)
  #deep copy of graph to spg(shortest path graph)
  for i in range(0,v):
    spg.append([])
    for j in range(0,v):
      spg[i].append(graph[i][j])
  
  #floyd warshall algorithm
  for k in range(0,v):
    for i in range(0,v):
      for j in range(0,v):
        spg[i][j]=min(spg[i][j],spg[i][k]+spg[k][j])
  #return resultant graph
  return spg

#Providing random no.of vertices 
V=rand.randint(2,15)
INF=99999

undirected_graph=[]
#Generating random graph in adjacency matrix
for i in range(0,V):
  undirected_graph.append([])
  for j in range(0,V):
    undirected_graph[i].append(INF)

for i in range(0,V):
  for j in range(i+1,V):
    e=rand.randint(0,1)
    if e==1:
      w=rand.randint(2,500)
      undirected_graph[i][j]=w
      undirected_graph[j][i]=w

spg=floydWarshall(undirected_graph)
file=open("graph_report.txt",'w')
file.write("Graph Report\n\n")
file.write("Undirected graph generated:\n\n")
for i in range(0,V):
  file.write(" \t\t"+str(i+1))
file.write("\n")
for i in range(0,V):
  file.write(str(i+1)+"\t\t")
  for j in range(0,V):
    if undirected_graph[i][j]==INF:
      file.write("INF\t\t")
    else:
      file.write(str(undirected_graph[i][j])+"\t\t")
  file.write("\n")
file.write("\nNote:INF Means no path\n")
file.write("     SPB means Shortest Path Between\n\n")
for i in range(0,V):
  for j in range(i+1,V):
    if spg[i][j]<INF:
      file.write("SPB "+str(i+1)+" and "+str(j+1)+" is "+str(spg[i][j])+"\n")
file.close()

Sample Output: