Menor caminho do Grafo passando por todos os pontos

Afim de se obter o menor caminho passando por todos os pontos, modificou-se a classe GMain da seguinte forma:

import java.io.*;

import java.util.*;

public class Gmain {

static final int UNVISITED = 0;

static final int VISITED = 1;

static int c1[] = new int[20];

static int c2[] = new int[20];

static int c3[] = new int[20];

static int c4[] = new int[20];

static int[] minPath = new int[10];

static int p1 = 0;

static int p2 = 0;

static int p3 = 0;

static int p4 = 0;

static int p5 = 0;

static Graph createGraph(DataInputStream file) throws IOException {

String line;

StringTokenizer token;

boolean undirected = false;

int i, v1, v2, weight;

Assert.notNull(line = file.readLine(),

"Unable to read number of vertices");

while(line.charAt(0) == '#')

Assert.notNull(line = file.readLine(),

"Unable to read number of vertices");

token = new StringTokenizer(line);

int n = Integer.parseInt(token.nextToken());

Graph G = new Graphl(n);

Assert.notNull(line = file.readLine(),

"Unable to read graph type");

if (line.charAt(0) == 'U')

undirected = true;

else if (line.charAt(0) == 'D')

undirected = false;

else Assert.notFalse(false, "Bad graph type: " + line);

while((line = file.readLine()) != null) {

token = new StringTokenizer(line);

v1 = Integer.parseInt(token.nextToken());

v2 = Integer.parseInt(token.nextToken());

if (token.hasMoreTokens())

weight = Integer.parseInt(token.nextToken());

else

weight = 1;

G.setEdge(v1, v2, weight);

if (undirected)

G.setEdge(v2, v1, weight);

}

return G;

}

static void graphOp(Graph G) {

int[] D = new int[G.n()];

Dijkstra(G, 0, D);

for (int i=0; i<G.n(); i++)

System.out.println("Vertex " + i + " is at distance " + D[i]);

printMatrix(c1);

printMatrix(c2);

printMatrix(c3);

printMatrix(c4);

printMatrix(minPath);

makePath(c1, p1);

makePath(c2, p2);

makePath(c3, p3);

makePath(c4, p4);

}

static int minVertex(Graph G, int[] D) {

int v = 0;

for (int i=0; i<G.n(); i++)

if (G.getMark(i) == UNVISITED) { v = i; break; }

for (int i=0; i<G.n(); i++)

if ((G.getMark(i) == UNVISITED) && (D[i] < D[v]))

v = i;

return v;

}

static void Dijkstra(Graph G, int s, int[] D) {

for (int i=0; i<G.n(); i++)

D[i] = Integer.MAX_VALUE;

D[s] = 0;

for (int i=0; i<G.n(); i++) {

int v = minVertex(G, D);

minPath[p5] = v;

p5++;

System.out.println ( "Vertex : " + Integer.toString(v));

G.setMark(v, VISITED);

if (D[v] == Integer.MAX_VALUE) return;

for (Edge w = G.first(v); G.isEdge(w); w = G.next(w))

if (D[G.v2(w)] > (D[v] + G.weight(w)))

{

D[G.v2(w)] = D[v] + G.weight(w);

System.out.println("Nodes: "+Integer.toString(G.v2(w))+" "+Integer.toString(G.v1(w)));

if (G.v2(w)==1)

{

c1[p1] = G.v1(w);

p1++;

c1[p1] = G.v2(w);

}

else if (G.v2(w)==2)

{

c2[p2] = G.v1(w);

p2++;

c2[p2] = G.v2(w);

}

else if (G.v2(w)==3)

{

c3[p3] = G.v1(w);

p3++;

c3[p3] = G.v2(w);

}

else if (G.v2(w)==4)

{

c4[p4] = G.v1(w);

p4++;

c4[p4] = G.v2(w);

}

printMatrix(D);

}

}

}

public static void main(String args[])

throws FileNotFoundException, IOException {

DataInputStream f;

if (args.length == 0)

f = new DataInputStream(System.in);

else

f = new DataInputStream(new FileInputStream(args[0]));

Graph G = createGraph(f);

for (int i=0; i<G.n(); i++)

G.setMark(i, UNVISITED);

graphOp(G);

System.in.read();

}

public static void printMatrix(int[] matrix)

{

for ( int count = 0; count < matrix.length; count++ )

{

if (matrix[count]==Integer.MAX_VALUE) System.out.print("0 ");

else System.out.print(matrix[count]+" ");

}

System.out.println("");

}

public static void makePath(int[] matrix, int pos)

{

int temp = matrix.length-1;

int v1 = 0;

int v2 = 0;

int w1 = 0;

int w2 = 0;

boolean done = false;

while(temp!=0)

{

v1 = matrix[pos];

v2 = matrix[pos-1];

w1 = minPath[temp];

w2 = minPath[temp-1];

if ((v1==w1)&&(v2==w2))

{

System.out.print("Path: ");

while (temp!=0)

{

System.out.print(Integer.toString(minPath[temp])+" ");

temp--;

done = true;

}

System.out.println("");

}

if(done==false) temp--;

else temp = 0;

}

if(done==false)

{

temp = pos;

System.out.print("Path: ");

while(temp>=0)

{

System.out.print(Integer.toString(matrix[temp])+" ");

temp--;

done = true;

}

}

}

}