Editorials of CTSHT in UVCE NCode 2013

general
, , , ,
1

PROBLEM LINK:

Practice

Contest

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
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.

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]