global Arguments
  int n, w
  string[20] fname
body Arguments
  getarg(1, n); getarg(2, w); getarg(3, fname)
end

global Shared
  import Arguments
  op bag(int path[1:*], int hops, int length)  # partial tours
  int dist[1:n,1:n]                # distances
  int  shortest = 2**30            # best so far
  op update(int path[1:*], int length)     # update shortest
body Shared
  file fd = open(fname, READ)
  for [ i = 1 to n, j = 1 to n ] { read(fd, dist[i,j]) }
  int  shortest_path[1:n]
  sem mutex = 1

  proc update(path, length)  {
    P(mutex)
      if (length < shortest) {
	shortest = length; shortest_path = path
      }
    V(mutex)
  }

  final {
    write("the shortest path has length", shortest)
    write("the cities on the shortest path are:")
    writes("  ")
    for [ i = 1 to n ] { writes(shortest_path[i], " ") }
    write()
  }
end

resource Worker()
  import Arguments, Shared

  # extend path to include city if city has not yet been visited
  procedure extend_path(int city, var int path[1:*], int hops, int length)
			returns int newlength {
    for [ i = 2 to hops st path[i] == city ] { newlength = 0; return }
    newlength = length + dist[path[hops], city]; path[hops+1] = city
  }

  process worker  {
    int  path[1:n], hops, length, newlength
    while (true) {
      receive bag(path, hops, length)
      for [ city = 2 to n ] {
	newlength = extend_path(city, path, hops, length)
	if (newlength == 0) { next }    # city has been visited
	if (hops+1 < n and newlength < shortest) {
	    # put partial tour back into bag for further processing
	    send bag(path, hops+1, newlength)
	} else if (hops+1 == n ) {
	    # add distance back to city 1
	    newlength = newlength + dist[path[n],1]
	    if (newlength < shortest) {
	      # this tour is possibly the best
	      update(path, newlength)
	    }
	}
      }
    }
  }
end Worker

resource Main()
  import Arguments, Shared, Worker
  # generate first set of partial tours and put them into bag
  int  path[1:n] = (1, [n-1] 0)
  for [ i = 2 to n ] {
    path[2] = i
    send bag(path, 2, dist[1,i])
  }
  # create worker processes
  for [ i = 1 to w ] { create Worker() }
end Main