4.3.4. Algoritmos sobre grafos dirigidos.
Nodo más central de un grafo dirigido con pesos
Excentricidad de un vértice v en un grafo con pesos: es el valor máximo de las longitudes mínimas de los caminos desde todos los nodos hasta el nodo v. Es la distancia para el nodo más alejado.
excentricidad(v) = máx {longitud mínima de los caminos de w a v, para w ? V}
Nodo más central de un grafo dirigido con pesos: es el nodo con valor de excentricidad mínimo.
Cálculo del nodo central de un grafo:
- 1. Calcular la distancia mínima entre cada par de nodos, utilizando el algoritmo de Floyd (o Dijkstra repetido n veces). Obtener una matriz de costes mínimos.
- 2. Calcular las excentricidades. excentricidad(v)= max {C[w, v] | ? w ? V}
- 3. Devolver el nodo con menor valor de excentricidad.
¿Cuál es el orden de complejidad del algoritmo?