Matriz de distancias y Dijkstra

[xiruko]

Hola,

estoy tratando de resolver un ejercicio de encontrar el camino más corto entre varios nodos y he pensado en hacerlo con el algoritmo de Dijkstra. El problema es que no sé como construir la matriz de distancias entre los distintos nodos.

Como entrada me llega una matriz de carácteres, donde cada carácter representa algo:

O O O N
O X O X
N X O X
O X S X

O -> Camino libre
X -> Obstáculo
S -> Nodo inicial
N -> Nodos por los que tengo que pasar

El tablero en este caso es 4x4 pero puede ser de cualquier dimensión hasta 100. Así que bueno... Alguien sabe algún método eficiente para construir la matriz de distancias entre los distintos nodos?

Gracias!

[SnzCeb]

Antes de nada, buscas hacerlo de un nodo a los demás únicamente, ¿De qué naturaleza son los grafos con los que vas a tratar? (Densos, dispersos . ..) ¿Hay caminos negativos?