Busca do caminho mais curto em um grafo usando classes

PHP Hard classes

Tarefa «Busca do caminho mais curto em um grafo usando classes»

Implemente a classe Graph para representar um grafo direcionado ponderado. A classe deve conter os métodos addEdge(int $from, int $to, int $weight) para adicionar uma aresta e shortestPath(int $start, int $end) para encontrar o caminho mais curto do vértice $start até $end usando o algoritmo de Dijkstra. Se o caminho não existir, o método deve retornar -1. É garantido que os pesos das arestas são positivos, o número de vértices não excede 1000 e o número de arestas é de até 10000.

Formato de Entrada

Na primeira linha, separados por espaço, são informados N (número de vértices) e M (número de arestas). Nas M linhas seguintes, as arestas são informadas no formato: from to weight. Na última linha, são informados start e end.

Formato de Saída

Um número inteiro — o custo mínimo do caminho de start até end, ou -1, se o caminho não existir.

Exemplos

Exemplo 1

ENTRADA

10

SAÍDA

87

Exemplo 2

ENTRADA

SAÍDA

15

Exemplo 3

ENTRADA

1

SAÍDA

0

Exemplo 4

ENTRADA

1
2 7
1

SAÍDA

-1

main.php