fork download
copy 
  1. def Greedy(nodes, matrix):
  2.  
  3.     BIG = 99999
  4.     cost = 0
  5.     node = 0
  6.     start = node
  7.     explored = [ 0 ] * (nodes+1)
  8.     explored[node] = 1
  9.  
  10.     print(node+1, end = " ")
  11.  
  12.     for i in range(1, nodes):
  13.  
  14.         min = BIG
  15.  
  16.         for vertice in range(0, nodes):
  17.  
  18.             if matrix[node][vertice] != 0 and explored[vertice] == 0 and matrix[node][vertice] < min:
  19.  
  20.                 min = matrix[node][vertice]
  21.  
  22.                 next = vertice
  23.  
  24.         explored[next] = 1
  25.  
  26.         print(next+1, end = " ")
  27.  
  28.         cost = cost + matrix[node][next]
  29.  
  30.         node = next
  31.  
  32.     cost = cost + matrix[start][node]
  33.  
  34.     print(start+1, end = " ")
  35.  
  36.     print("\nCost =", cost)
  37.  
  38. def readMatrix():
  39.     matrix = [[5],[0,1,5,5,3],[1,0,2,4,1],[5,2,0,6,1],[5,4,6,0,9],[3,1,1,9,0]]
  40.     nodes = int(matrix.pop(0)[0])
  41.     for i in range(nodes):
  42.         for j in range(nodes):
  43.             print(matrix[i][j], end =" ")
  44.         print()
  45.     print()
  46.     return nodes, matrix
  47.  
  48. def readMatrixStd():
  49.     nodes = int(input("nodes="))
  50.     matrix = [[0 for j in range(nodes+1)] for i in range(nodes+1)]
  51.     for i in range(0, nodes):
  52.         for j in range(0, nodes):
  53.             matrix[i][j] = int(input("matrix[%d][%d]="%(i,j)))
  54.  
  55.     for i in range(nodes):
  56.         for j in range(nodes):
  57.             print(matrix[i][j], end =" ")
  58.         print()
  59.  
  60.     print()
  61.  
  62.     return nodes, matrix
  63.  
  64. def ReadFileMatrixAdjacency(filename):
  65.  
  66.     with open(filename, "r") as file:
  67.         matrix = [ [int(j) for j in line.split(" ")] for line in file]
  68.  
  69.     nodes = int(matrix.pop(0)[0])
  70.     for i in range(nodes):
  71.         for j in range(nodes):
  72.             print(matrix[i][j], end =" ")
  73.         print()
  74.     print()
  75.     return nodes, matrix
  76.  
  77. def fn():
  78.     filename = "salesman.in"
  79.     #data = ReadFileMatrixAdjacency( filename )
  80.     #data = readMatrix()
  81.     data = readMatrixStd()
  82.     nodes = data[0]
  83.     matrix = data[1]
  84.     Greedy(nodes, matrix)
  85. fn()
  86.  
Success #stdin #stdout 0.03s 9748KB
comments (?)
stdin
copy 
5
0 
1
5 
5 
3
1 
0 
2 
4 
1
5 
2 
0 
6 
1
5 
4 
6 
0 
9
3 
1 
1 
9 
0
stdout
copy 
nodes=matrix[0][0]=matrix[0][1]=matrix[0][2]=matrix[0][3]=matrix[0][4]=matrix[1][0]=matrix[1][1]=matrix[1][2]=matrix[1][3]=matrix[1][4]=matrix[2][0]=matrix[2][1]=matrix[2][2]=matrix[2][3]=matrix[2][4]=matrix[3][0]=matrix[3][1]=matrix[3][2]=matrix[3][3]=matrix[3][4]=matrix[4][0]=matrix[4][1]=matrix[4][2]=matrix[4][3]=matrix[4][4]=0 1 5 5 3 
1 0 2 4 1 
5 2 0 6 1 
5 4 6 0 9 
3 1 1 9 0 

1 2 5 3 4 1 
Cost = 14
https://ideone.com/FaCJms
Salesman
language:
Python 3 (python  3.9.5)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!