(*	Insertion Algorithm for Travelling Salesman problem

	INPUT	: The associated datafile is FitspDatafile.
		  1st # represents number of nodes in the given network
		  2nd # represents the starting node.
		  3rd set of numbers represent NxN weight matrix of the 
			network.

	OUTPUT	: 1. Given an approximate tour for travelling salesman
			route;  Route[I] is the Ith node visited and 
			Route[1] is the starting node S.
		  2. Total weight cost of the tour.

	Algorithm : The FISTP procedure computes an approximate tour
		    for the travelling salesman problem, in a complete
		    directed network of N nodes.  The starting node S 
		    is also specified.  The execution time depends 
		    on the size of the network.  The time for one
		    call of FITSP grows as O(n^2) and for n calls it
		    grows as O(n^3).
		    The FISTP works as follows :
		    1. Pick a city as the starting node, say S, of the 
			tour.
		    2.From among the remaining (n-1) cities it selects 
			another city, to be included in this tour.
		      The selection of next node to be included in this
			tour involve two steps.
		      (a) Selection step.  In the set V-Vt of unvisited
			  nodes, determine which node is to be added to the
			  cycle next.  The heuristic used is farthest
  			  insertion.
		      (b) Insertion step.  Determine when the newly selected
			  node is to be inserted to enlarge the current
			  subtour.
							*)
 
program Farthest_Insertion (input,output,FitspDatafile,FitspOutfile);

const	maxvar = 50;

type	CHARFILE = file of char;
	ARRN = array [1..maxvar] of integer;
	ARRNB = array [1..maxvar] of boolean;
	ARRNN = array [1..maxvar,1..maxvar] of integer;

var	N : integer;
	S : integer;
	Nextint : integer;
	INF : integer;
	W : ARRNN;
	ROUTE : ARRN;
	TWEIGHT : integer;
	FitspDatafile : CHARFILE;
        FitspOutfile  : CHARFILE;


procedure Infile (var N : integer;
		  var INF : integer;
		  var S : integer;
		  var W : ARRNN;
		  var Nextint : integer);

var row, column : integer;

begin
  reset (FitspDatafile);
  readln (FitspDatafile,Nextint);
  N := Nextint;
  readln (FitspDatafile,Nextint);
  S := Nextint;
  readln (FitspDatafile,Nextint);
  INF := Nextint;
  for row := 1 to N do
  begin
    for column := 1 to N do
    begin
      read(FitspDatafile,Nextint);
      W[row,column] := Nextint;
    end;
    readln(FitspDatafile);
  end;
end;



procedure FITSP(
       N,S,INF:integer;
   var W      :ARRNN;
   var ROUTE  :ARRN;
   var TWEIGHT:integer);

   var end1,end2,FARTHEST,I,INDEX,
          INSCOST,J,MAXDIST,NEWCOST,NEXTINDEX :integer;
       CYCLE,DIST                             :ARRN;
begin
   for I:=1 to N do CYCLE[I]:=0;
   CYCLE[S]:=S;
   for I:=1 to N do DIST[I]:=W[S,I];
   TWEIGHT:=0;
   for I:=1 to N-1 do begin
      MAXDIST:=-INF;
      for J:=1 to N do
         if CYCLE[J] = 0 then
            if DIST[J] > MAXDIST then begin
               MAXDIST:=DIST[J];  FARTHEST:=J
            end;
      INSCOST:=INF;  INDEX:=S;
      for J:=1 to I do  begin
         NEXTINDEX:=CYCLE[INDEX];
         NEWCOST:=W[INDEX,FARTHEST]+W[FARTHEST,NEXTINDEX]-
                  W[INDEX,NEXTINDEX];
         if NEWCOST < INSCOST then begin
            INSCOST:=NEWCOST;
            end1:=INDEX;  end2:=NEXTINDEX
         end;
         INDEX:=NEXTINDEX
      end;  { for J }
      CYCLE[FARTHEST]:=end2;  CYCLE[end1]:=FARTHEST;
      TWEIGHT:=TWEIGHT+INSCOST;
      for J:=1 to N do
         if CYCLE[J] = 0 then
            if W[FARTHEST,J] < DIST[J] then DIST[J]:=W[FARTHEST,J]
   end;  { for I }
   INDEX:=S;
   for I:=1 to N do begin
      ROUTE[I]:=INDEX;  INDEX:=CYCLE[INDEX]
   end
end;  { FITSP }


procedure Outfile(ROUTE : ARRN;
		  TWEIGHT : integer);

var count : integer;

begin
  rewrite(FitspOutfile);
  writeln (FitspOutfile,'The route for tsp using  Farthest Insertion algorithm is path  ');
  for count := 1 to N do
  begin
    write (FitspOutfile,ROUTE[count]);
  end;
  writeln(FitspOutfile);
  writeln (FitspOutfile,'with total weight of ',TWEIGHT);
end;


begin (* main *)
  Infile (N,INF,S,W,Nextint);
  FITSP(N,S,INF,W,ROUTE,TWEIGHT);
  Outfile(ROUTE,TWEIGHT);
end.