Author: Bharathkumar Hegde
Tester: Amogh Aithal
Editorialist: Bharathkumar Hegde
Basic knowledge of graph theory
Given the information about the direct connections between the cities in a country. You are asked to find out the shortest distance
between the given set of cities.
This problem is straight forward question on Floyd’s Algorithm.
Apply Floyd’s algorithm on the given matrix and answer the queries with the new matrix.
Floyd’s algorithm is the method to find out shortest distances between all pairs of the cities. This algorithm selects all nodes one by one say
kth node , for each kth node all possible pairs of nodes, say ith and jth nodes, are selected and checked whether
the distance between ith and jth node can be reduced if we go through the kth node.
In this problem nodes are cities.
def floyds_algorithm( ditance_matrix ): for k from 1 to n : for i from 1 to n: for j from 1 to n: if distance_matrix[i][j] > distance_matrix[i][k] + distance_matrix[k][j] : // if the distance between ith node and jth node can be reduced with new path i->k->j , // then set the shortest distance to cost of new path. distance_matrix[i][j] = distance_matrix[i][k] + distance_matrix[k][j]