Pow cara, não é por nada, mas acho que isso não funciona, na real eu te afirmo que não vai funcionar já, pois comentando essas linhas, o método minimalNontight fica errado, digo isso porque só de olhar ele ja da para ver que ele não iria fazer uma coisa lógica, na real isso pega simplesmente o primeiro nó não visitado e escolhe ele, o que para esse problema não é lógico:
private int minimalNontight()
{
int j, u;
for (j = FIRST_VERTEX; j < LAST_VERTEX; j++)
{
if (!tight[j]) break;
}
assert (j <= LAST_VERTEX);
u = j;
return u;
}
Outra, o grafo que vc fez tb é muito simples, tem dois caminhos só para chegar de v1 a v6, então se seu algoritmo fizer uma coisa errada, mas que chegue no final, ele vai ter 50% de chance de acertar e vc pensar que ele esta certo…testa com aquele grafo do algoritmo que vc pegou (com LAX, LGA, etc), ele é maior e vc vai poder testar mais situações. Mas… ai vai minhas considerações: eu acho que Dijkstra não serve para caminho mais longo. Porque?! porque no final do processamento do algoritmo, vc tem informação de melhor caminho do nó de origem para todos nós do grafo, já que ele sempre vai para a nó com menor peso a partir do nó de origem, e marcando esse nó como “visitado”, ele sabe que para aquele nó ele descobriu o melhor caminho. No caso do caminho mais longo isso não é verdade, se eu partir para o nó com aresta de maior peso, não posso marcar como visitado, pois posso pegar uma aresta com peso mais curto e dar uma volta em todo grafo para chegar naquele que é meu visinho, logo, não tem como usar a mesma logica de processamento para caminho mais longo. Ex:
Usando as mesmas cidades e ligações que o grafo do algoritmo de Dijkstra que vc passou, mas alterando alguns pesos:
LAX para ORD tem distancia de 1743km
LAX para SFO tem distancia de 337km
SFO para ORD tem distancia de 1843km
ORD para DFW tem distancia de 800km
LAX para DFW tem distancia de 4000km
Fazendo o melhor caminho a partir de LAX até DFW… o algoritmo vai analisar os visinhos de LAX e vai descobrir que pode chegar a DFW em 4000km, a SFO em 337km e ORD em 1743km, a menor distancia é para SFO, então ele tem certeza que até SFO ele não consegue chegar por um caminho mais curto, pois para ir para qualquer cidade visinha já é mais longe, logo ele vai partir para SFO e marcar essa cidade como visitada. Chegando em SFO, ele vai analisar os visinhos não visitados, no caso ORD, e vai descobrir que para chegar em ORD a partir de SFO seriam necessários 337km + 1843km, que é maior que a distancia atual de ORD que é de 1743km, logo ele não altera nada e SFO fica por isso. Ai vai analisar de novo os menores caminhos de distancia, agora tenho 2 nós ainda não visitados, DFW com distancia 4000km e ORD com distancia 1743km, escolhe ORD, marca ele como visitado (significa, achei o melhor caminho para ORD) e descubro que a partir de ORD da para chegar em DFW com 1743km + 800km, menor que os 4000km atuais, logo altero DFW para a nova distancia passando por ORD (2543km), por ultimo, só existe DFW não marcado, analisa ele, e nada se altera nas distancias. Concluindo, tenho o menor caminho para todos nós do grafo partindo de LAX.
Agora a mesma logica não funciona para o caminho mais longo, pois não posso partir para o nó mais longo e marcar ele como visitado, já que não tenho certeza que realmente é o mais longo. Por exemplo, vou mudar o grafo para ficar mais facil de entender (pq fatalmente para aquele ali daria certo heheh), mas tirando fora a cidade DFW, eu teria o seguinte grafo:
LAX para ORD tem distancia de 1743km
LAX para SFO tem distancia de 337km
SFO para ORD tem distancia de 1843km
Se quizesse chegar pelo maior caminho de LAX até ORD, considerando o maior caminho, o sistema iria visitar primeiro o nó ORD (mais distante) e marca-lo (como se pensasse: pronto, ja achei pro ORD), quando o maior caminho é passando por SFO, na real o grande problema ai tá num clico que no melhor caminho vc não tem. O maior caminho para chegar em ORD é por SFO e o maior caminho para chegar em SFO é por ORD, então seria mais ou menos como eu te dizer: olha, para vc chegar em ORD, vai por SFO, ai vc diz: “blz, então como chego em SFO”, ai eu respondo: “vai por ORD”… então acho que não da de usar a mesma logica de Dijsktra, pois minha solução não teria maiores caminhos para todos do grafo e sim maior caminho apenas para aquele que eu quero. Com certeza tem um algoritmo para calculo do caminho mais longo, pode até ser uma variação de Dijsktra, mas acho que as alterações são mais significantes. Da uma olhada em Pert e CPM. De qualquer forma, eu fiz um que calculo é feito através da busca em uma árvore por largura, se interessar, usei algumas coisas daquele Dijkstra. Basicamente a idéia é: o caminho mais longo entre x e y, é o caminho mais longo entre um dos sucessores de x até y + a soma do caminho de x até o sucessor.
public class Teste
{
// define some constants
public static final int INF = Integer.MAX_VALUE; // infinity
// now define the cities
public static final int HNL = 0;
public static final int SFO = 1;
public static final int LAX = 2;
public static final int ORD = 3;
public static final int DFW = 4;
public static final int LGA = 5;
public static final int PVD = 6;
public static final int MIA = 7;
public static final int nonexistent = 8;
// start and end vertices
public static final int FIRST_VERTEX = HNL;
public static final int LAST_VERTEX = MIA;
// list of names of cities, for output
private String[] name = { "HNL", "SFO", "LAX", "ORD", "DFW", "LGA", "PVD", "MIA" };
// now the initial distance matrix ("weight")
private int weight[][] = {
/* HNL SFO LAX ORD DFW LGA PVD MIA */
{ 0, INF, 2555, INF, INF, INF, INF, INF }, // HNL
{ INF, 0, 337, 1843, INF, INF, INF, INF }, // SFO
{ 2555, 337, 0, 1743, 1233, INF, INF, INF }, // LAX
{ INF, 1843, 1742, 0, 802, INF, 849, INF }, // ORD
{ INF, INF, 1233, 802, 0, 1387, INF, 1120 }, // DFW
{ INF, INF, INF, INF, 1387, 0, 142, 1099 }, // LGA
{ INF, INF, INF, 849, INF, 142, 0, 1205 }, // PVD
{ INF, INF, INF, INF, 1120, 1099, 1205, 0 }, // MIA
};
private boolean successor(int u, int z)
{
return ((weight[u][z] != INF) && u != z);
}
public static void main(String[] unused)
{
new Teste().caminho(HNL, DFW);
}
private Stack<Integer> pilha = new Stack<Integer>();
void caminho(int de, int para)
{
Noh result;
try
{
result = maiorCaminho(de, para);
}
catch (NonExistentException e)
{
System.out.println(name[de] + " não esta conectado a " + name[para]);
return;
}
for (Noh temp = result; temp.next != null; temp = temp.next)
{
System.out.print(name[temp.currentNoh] + " - ");
}
System.out.println("Distancia: " + result.dist);
}
class Noh
{
public int currentNoh;
public int dist;
public Noh next;
public Noh (int currentNoh, int dist, Noh next)
{
this.currentNoh = currentNoh;
this.dist = dist;
this.next = next;
}
}
/**
* Exceção que significa que não existe caminho entre os dois nós
*/
class NonExistentException extends Exception
{
private static final long serialVersionUID = -186766560634665571L;
}
/**
* Acha o maior caminho entre um nó origem e destino
*/
Noh maiorCaminho(final int src, final int dest) throws NonExistentException
{
if (src == dest)
{
// chegou ao nó de destino, ele não tem next (null) e sua distancia é 0
return new Noh(dest, 0, null);
}
// cria lista de sucessores do nó de origem
final List<Integer> sucessores = new ArrayList<Integer>();
for (int z = FIRST_VERTEX; z <= LAST_VERTEX; z++)
{
if ((successor(src, z)) && (!pilha.contains(z)))
{
sucessores.add(z);
}
}
// pilha para evitar visitar o mesmo sucessor (evita ciclos)
pilha.push(src);
// calcula o maior caminho entre cada sucessor e o destino, descobrindo assim o sucessor do nó. O sucessor do nó de origem sera o sucessor que
// tiver maior distancia desde o nó de origem + a maior distancia entre ele e o nó destino
Noh mSucessor = null;
for (Integer sucessor : sucessores)
{
try
{
Noh to = maiorCaminho(sucessor, dest);
int distSucessor = weight[src][sucessor] + to.dist;
if ((mSucessor == null) || (mSucessor.dist == INF) || (distSucessor > mSucessor.dist))
{
mSucessor = new Noh(sucessor, distSucessor, to);
}
}
catch (NonExistentException e)
{
// por esse sucessor não chega no destino
continue;
}
}
pilha.pop();
if (mSucessor == null)
{
// não tem como chegar de src até dest
throw new NonExistentException();
}
return mSucessor;
}
}
