This C++ code implements a real time use case of Floyd-Warshall algorithm to compute the shortest paths between all pairs of locations on the IIT Kharagpur campus map.
The algorithm is optimized by using dynamic programming technique memoization to store previous stops to reach a location.
30 locations have been considered, as shown in the image of the map. Considering each location a node, an integer value starting from 1 is assigned.
When the user chooses to enter source and destination, Floyd-Warshall algorithm is applied and it generates the minimum distances for every pair of locations. When the user now enters source and destination, along with the minimum distance between the given source and destination, the shortest path to be taken in order to achieve the minimum distance is also displayed.
Node number Location
1 Main Building
2 SN/IG Hall
3 MT Hall
4 RLB Hall
5 CCD/Heritage
6 Jnan Ghosh Stadium
7 Gymkhana/Axis Bank ATM
8 Lake
9 Swimming Pool
10 B C Roy Hall
11 A M Hall
12 Gokhale Hall
13 V S Hall
14 J C B Hall
15 H J B Hall
16 Patel Hall
17 LBS Hall
18 MMM Hall
19 LLR Hall
20 MS Hall
21 RK Hall
22 RP Hall
23 SNVH Hall
24 Technology Guest House
25 Director's Bunglow
26 B C Roy Hospital
27 Technology Market
28 Tikka/Clock Tower
39 Tata Steel Complex
30 Tagore Open Air Theater