Algoritmia - URGENTE; grafos: caminos MAXIMOS

Necesito averiguar cómo obtener los caminos máximos en un grafo representado por su matriz de conexiones, en la que un 1 indica que hay una arista que une los nodos y un 0 que no hay arista.
URGENTE.

Disculpa mi ignorancia... que es un camino MAXIMO en un grafo?

Los caminos maximos de un grafo se obtienen con el algoritmo de
dijkstra lo unico ,que tenes que invertir la pregunta o sea en vez de tomar
el camino si es mejor lo tomas si es peor ( si las aristas son todas negativas sigue siendo el algoritmo de disjtra).

Cualquier cosa escribime que te ayudo......

Como modifico el algoritmo de Disjtra para que admita "pesos" de aristas negativas. Ej todas a -1.

es igual al algoritmo de tree??? estoy buscando inf y no encuentro

Cambiar la pregunta en el algoritomo de Dijkstra... no funcion (es decir, en vez de tomar minimos, tomar maximos..) y otra cosa es que el algoritmo de Dijsktra no funciona con costos negativos, aunque sería interesante ver que sucede si todos los caminos son negativos... habría que ver que resulta en la induccion sobre esa hipotesis