SCHEME01-EDITORIAL

ravit007 · May 24, 2015, 11:30pm

Editorialist: Kartik Kapoor kartik07 | CodeChef User Profile for Kartik Kapoor | CodeChef

Medium

You are required to find the minimum amount that a person will have to pay if he is to travel

between 2 given places. The amount is calculated from the ‘points’ the person posseses at the end

of the trip, which are in-turn calculated from the distance the person travels.

This is a classic problem of finding the minimum distance between 2 places with a twist!!

The problem can be solved by applying Dijkstra's algorithm with a slight variation as to how the

distance between 2 adjacent nodes is calculated. The distance travelled is taken as the actual

distance between the nodes minus a given value. This is value is different for different nodes. The

value is subtracted only if the distance between a pair of nodes is more than the value to be

subtracted.

The problem requires you to find the minimum distance between 2 nodes in a directed graph. This

can be done by applying Dijkstra’s algorithm

.Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph. Here is

dijkstras-shortest-path-algorithm/)

Below are the detailed steps used in Dijkstra’s algorithm to find the shortest path from a single

source vertex to all other vertices in the given graph:

Algorithm

1) Create a set sptSet (shortest path tree set) that keeps track of vertices included in shortest path

tree, i.e., whose minimum distance from source is calculated and finalized. Initially, this set is empty.

2) Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE.

Assign distance value as 0 for the source vertex so that it is picked first.

3) While sptSet doesn’t include all vertices

….a) Pick a vertex u which is not there in sptSetand has minimum distance value.

….b) Include u to sptSet.

….c) Update distance value of all adjacent vertices of u. To update the distance values, iterate

through all adjacent vertices. For every adjacent vertex v, if sum of distance value of u (from source)

and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Finally you will need to modify the Dijkstra’s algorithm as follows:

The distance between 2 adjacent nodes is taken as the actual distance between the nodes minus a

given value. This is value is different for different nodes. The value is subtracted only if the distance

between a pair of nodes is more than the value to be subtracted.