¿Un algoritmo para reconstruir un gráfico a partir de su información de ruta más corta?

8

Tengo algunos datos de ruta más cortos para un gráfico. ¿Puedo reconstruir el gráfico a partir de estos datos?

Más precisamente, tengo una matriz booleana (0/1) para cada vértice v en el gráfico (V, E) . El elemento de matriz [s, d] es igual a 1 si v v está en la ruta más corta desde el vértice de origen s hasta el vértice de destino d . Todos los bordes en el gráfico tienen la misma longitud.

Por ejemplo, para el gráfico

(V1) -- (V2) -- (V3)

las tres matrices serían:

V1:

1 1 1
1 0 0
1 0 0

V2:

0 1 1
1 1 1
1 1 0

V3:

0 0 1
0 0 1
1 1 1

Mis preguntas:

1) ¿hay un algoritmo para reconstruir el conjunto de bordes E a partir de estas matrices?

2) ¿la solución es siempre única? (Esto es más una curiosidad personal que un requisito real)

3) ¿se puede generalizar el algoritmo a longitudes de borde no uniformes?

algorithms kfx
fuente
1
Si hay un borde entre dos vértices v1y v2, entonces exactamente estos dos vértices están en el camino más corto entre v1y v2. Entonces, para cualquier otro vértice v, [v1, v] == 0 == [v, v1]en la matriz de v2y [v2, v] == 0 == [v, v2]en la matriz de v1.
Giorgio
1
Tal vez estoy equivocado, pero ¿no son 1) y 2) equivalentes?
proskor
No estoy seguro de si 1) y 2) son equivalentes: puede haber más de un gráfico para una determinada información de ruta más corta y también un algoritmo que encuentre todas las soluciones posibles.
Giorgio
Ok, pero ese es un problema diferente. El objetivo era reconstruir un gráfico a partir del conjunto de estas matrices, no calcular si hay una solución que satisfaga las restricciones codificadas en estas matrices.
proskor
1
@Giorgio al agregar un solo borde de v1 a v3 que es más largo que v1-v2-v3 da como resultado el mismo conjunto de matrices a menos que me falte algo, por lo que sería un contraejemplo para el caso de borde no uniforme
jk.

Respuestas:

2

puede extraer la matriz de adyacencia de las matrices de ruta utilizando la siguiente propiedad.

Hay un borde entre 2 vértices sy d si y solo si el camino más corto entre ellos contiene solo sy d.

Para una longitud no uniforme, solo obtendrá la solución única si se mantiene la desigualdad del triángulo . De lo contrario, un gráfico con d(p1,p2)=1 d(p2,p3)=2y d(p1,p3)=4mostrará la ruta más corta entre p1y p3como a través en p2lugar de la conexión directa. Lo que significa que el borde [p1, p3] nunca será parte de una ruta más corta.

monstruo de trinquete
fuente