Dado um mapa contendo os possíveis caminhos (arestas) para cada ponto (vértice), encontrar o menor caminho entre dois pontos e calcular o custo.
O Algoritmo de Dijkstra é um dos algoritmos que calcula o caminho de custo mínimo entre vértices de um grafo. Escolhido um vértice como raiz da busca, este algoritmo calcula o custo mínimo deste vértice para todos os demais vértices do grafo. Ele é bastante simples e com um bom nível de performance.
Para este problema foram utilizadas as seguintes tecnologias:
- Node.js
- MongoDB
Node.js para as requisições no formato REST. MongoDB para a persistência dos mapas.
Para executar o projeto é apenas necessário executar
npm start
O serviço disponibiliza duas urls, ambas via POST
/rest/map recebe o mapa em JSON no seguinte formato
{ "name" : "sp", "a" : { "b" : "1", "c" : "12" }, "b" : { "c" : "3", "a" : "1" } }
/rest/map/shortestPath recebe os parâmetro para calculo de rota em JSON no seguinte formato
{"name" : "sp", "source" : "a", "destiny" : "c", "autonomy" : 6.5, "price" : 10}
Existem duas possíveis respostas
{"path":["a","b","c"],"cost":"6.15"}
Para os casos onde existe um caminho
{"path":"unreacheable","cost":-1}
Para os casos em que não existe um caminho