Partners
DocsPalFree online file Converter and Viewer
|
|
Graph Center
Task:
Given a strongly connected graph. Find the vertex for which the length of shortest path to the farthest vertex is the smallest. This vertex
is called center of the graph.
Solution:
The solution is straight-forward: find the lengths of shortest paths between every pair of vertices, and then for each vertex find the length
of shortest path to the farthest vertex. Center of the graph is the vertex for which this value is minimal.
Floyd-Warshall algorithm may be used to find the lengths of shortest paths between
every pair of vertices, and the rest is trivial.
Algorithm:
- For each pair of vertices find the length of the shortest path between them.
- Find vertex i such that the length of shortest path to the farthest vertex is the smallest.
- Output vertex i found at step 2.
Pseudocode:
# N - number of vertices
# A(i,j) - length of the shortest path from vertex i to j
Compute all elements of A (by the help of Floyd-Warshall algorithm)
# dist(i) - length of shortest path from i to its farthest vertex
For i = 1 to N
dist(i) = 0
For j = 1 to N
If ( i != j AND A(i,j) > dist(i) ) Then dist(i)=A(i,j)
End For i
center = 1
For i = 1 to N
If dist(i) < dist(center) Then center = i
Output center
Complexity:
Complexity of this algorithm is determined by the part that finds the lengths of shortest paths between every pair of vertices.
Thus its complexity is O(N3).
Applications:
- Suppose that a hospital, a fire department, or a police department,
should be placed in a city so that the farthest point
is as close as possible. For example a hospital should be placed
in such a way that an ambulance can get as a fast as possible
to the farthest situated house (point).
|
Suppose that a new fire department should be constructed in this area of the city.
The best location would be the region that is situated as close as possible to the farthest point.
A way of finding such a region is by running Graph Center algorithm on selected vertices (regions).
Legend:
- vertex colored in dark-red represents the center of the graph
- number written on a vertex represents the length of the shortest path from center to that vertex
- number written on graph center vertex represents the length of shortest path to its farthest vertex |
|
|