## PROBLEM LINK:

**Author:** Bharathkumar Hegde

**Tester:** Amogh Aithal

**Editorialist:** Bharathkumar Hegde

## DIFFICULTY:

Simple

## PREREQUISITES:

Basic knowledge of graph theory

## PROBLEM:

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.

## QUICK EXPLANATION:

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.

## EXPLANATION:

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

*k ^{th}* node , for each

*k*node all possible pairs of nodes, say

^{th}*i*and

^{th}*j*nodes, are selected and checked whether

^{th}the distance between

*i*and

^{th}*j*node can be reduced if we go through the

^{th}*k*node.

^{th}In this problem nodes are cities.

Floyd’s Algorithm

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]