O Algoritmo de Dijkstra (Caminho mais Curto) em Java

English version at the following link:

enprogramminghome.blogspot.com

Olá pessoal,

Em link está um uma classe que programei que possui um único método search(type::TypeSearchEnum, v:int, cost:Graph<Double,Double>):SearchInfo

Vamos discutir a O.O deste método:
Esse método foi projetado para que diferentes tipos de buscas pudessem ser realizadas. A enumeração TypeSearchEnum tem somente o tipo "DIJKSTRA", pois somente programei
esse tipo de busca. Posteriormente, podemos inserir "BFS", "DFS","KRUSKAL",...

Se "TypeSearchEnum" é "DIJKSTRA" é chamado o método privado
-dijkstra(v:int, cost:Graph<Double,Double>):SearchInfo

Obviamente, este último método faz busca de Dijkstra em um grafo definido pela interface Graph&lK,V> (K = V = Double). Porque um objeto Graph<K,V>?
Eu poderia ter criado uma assinatura para cada tipo de grafo ex: "double[][] custos",
"LinkedList<LinkedList<Double>> custos", "ArrayList<ArrayList<Double>> custos", "ArrayList<LinkedList<Double>> custos"...

É possível pensar em uma quantidade enorme de assinaturas, o que implica em multiplicação de código. Agora, imagine que todos esses exemplos de grafos acima implementem uma interface "Graph<K,V>" que contém métodos de acesso apropriados a estrutura de dados. Assim, criando uma única assinatura podemos lidar com esse problema!!! (Polimorfismo pela interface)

Com essa aplicação percebe-se que nós saímos daquela idéia simplista de que uma interface é apenas um contrato. O que vimos acima é a vantagem das interfaces, um
polimorfismo inigualável.

O método acima retorna um objeto SearchInfo (explicarei esse objeto daqui a pouco) que contém os resultados da busca. Quais são esses resultados?
Evidentemente, cada vértice é representado por um inteiro. O resultado de uma busca a partir de um vertice "v" são os menores caminhos dele para TODOS os demais vértices. Um menor caminho não é baseado no número de vértices e sim na menor distância, então, é interessante que também sejam as menores distâncias. E são essas informações que SearchInfo armazena. Esta classe disponibiliza dois métodos públicos para consulta.

getPathFrom(vertex:int):LinkedList{Integer}

Este método retorna o menor caminho do vértice "v" para um vértice "vertex" do grafo. Uma linkedlist é usada devido as diferenças que podem existir no número de elementos em um caminho e também porque os elementos são inseridos por addFirst(e:E) (esse método executa em O(1)).

getPathFrom(vertex:int):double

Este método retorna a menor distância do vértice "v" para um vértice "vertex" do grafo.

A classe SearchInfo é interna a SearchGraphAlgorithms, pública e com construtor privado. Isso foi pensado da seguinte maneira:
Essa classe deveria conter um método que contruisse os caminhos a partir de um vetor de vértices anteriores gerado pelo método de dijkstra. Mas as pessoas não devem acessar esse método externamente, então, ele deveria ser privado. Contudo, a classe SearchGraphAlgorithms deve ser capaz de usar esse método de construção de caminhos, assim, a classe SearchInfo deve ser interna a SearchGraphAlgorithms.
SearchInfo deve ser pública para que código externo seja capaz de acessar os resultados da busca, contudo, o contrutor é criado a partir de uma vetor de menores distâncias gerado pelo método "dijkstra", então, o construtor deve ser privado a código externo e vísivel a SearchGraphAlgorithms, o que é possível pois SearchInfo é interno.

A interface Graph contém somente dois métodos:
+ get(i:int, j:int):V
+ size():int

Como aplicação, criei uma classe MatGraph que monta uma matriz de adjacência a partir de um arquivo formatado:
Ex:
8
0 * * * * * * *
30 0 * * * * * *
100 80 0 * * * * *
* * 120 0 * * * *
* * * 150 0 25 * *
* * * 100 * 0 90 140
* * * * * * 0 100
170 * * * * * * 0

A primeira linha deve conter o número de vértices. As demais linhas contêm as distâncias das adjacências. Quando não existir conexão o símbolo "*" deve ser inserido.

Na Classe Main está a aplicação desses códigos.

A numeração dos vértices começam a partir do zero.

Espero que tenham gostado!

Considerações finais:
Seja correto, caso você copie esse código no seu trabalho/projeto não deixe de indicar a minha autoria. Lembre-se que esse post é muito fácil de achar na internet e possui uma Orientação a Objetos um tanto peculiar, não seja uma pessoa tola.