Question

Part A (70 points) :

Write a program in a mall that will enable customers to reach the store they want to go to in the

shortest way. The coordinates of the some important stores in the mall are given below :

 Cinema: (256.6, 92.3)

 Sport Center: (120.5, 5.5)

 Restaurant: (350.0, 165.5)

 Cafe: (102.3, 10.26)

 Bowling: (40.8, 72.35)

 Clothes Store: (92.5, 86.4)

 Toy Store: (90.5, 302.1)

Roads connect these locations as below:

Program stores the road network as an adjacency matrix. Locations will be seen as numbers when

the program is opened. The user enters the starting position and the arrival position. And the

program calculates the shortest path and displays visited places to the user with total distance.

- Use adjacency matrix

- Use an algorithm for shortest path and explain it (part b)

- Display visited places

- Display the distance

Part B (30 points) :

 Explain which algorithm you use to calculate shortest path and how its work. You can use

text document or write as a comment at least one paragraph.

Note : As long as you do what is asked, you are free in the general structure, architecture and

which algorithm used. You explained it with comments or in a text file.

> Bro first of all, thank you for your help. It gives errors because there are missing parts in the source code. Screenshots are not clear, so I couldn't fix it. Any chance you can share the source code again?

Answer 1

The snapshots of the program source code and the output is provided below. The source code is provided at the end.

Note:-

1. To find the shortest path from the source node to the destination node, the dijkstra's algorithm has been used. In the Dijkstra's algorithm the program continuously updates the shortest path from the source node to the every node of the graph , until no more updations are possible. The "dijkstras()" function provided in the solution below , first determines the shortest distance and the shortest path from the source node to the destination node, and displays it in the console.

2. In the main function , the program prompts the user to enter the source and destination node, then the graph of the mall is created (in the form of adjacency matrix representation), and finally the "dijkstras()" function is called on this graph.

3. In the graph , the different locations in the mall are denoted by numbers from 0 to 6 and the order is similar to list of locations that is provided in the problem statement.

4. The distance between two nodes is calculated as the eucledian distance between the two nodes.

In case any problem is encountered while executing the program , inform in the comments.

1 2 3 4. 5 #include using namespace std; // 0. Cinema: (256.6,92.3) // 1. Sport Center: (120.5,5.5) // 2. Restaurant: (350.0, 165.5) // 3. Cafe: (102.3,10.26) // 4. Bowling: (40.8,72.35) // 5. clothes Store: (92.5,86.4) // 6. Toy Store: (90.5,302.1) 6 7 8 9 BE 10 11 12 13 // function to calculate the eucledian distance between two nodes string p1[7] = {"Cinema", "Sport Center", "Restaurant", "Cafe", "Bowling", "clothes Store", "Toy store"}; double calc_dist(double x, double y, double x1, double y1) { return sqrt(pow(x1-x,2)+pow(y1-y,2)); } 14 15 16 17 18 19 20 // applying dijkstras algorithm to find the shortest path from source to destination node void dijkstras (vector > adj,int u,int v) // u is source and v is destination { double dist[7]; // this array will store the shortest distance to any node i, from the source node int par[7]; // this array will store the parent to a node i int vis[7]; // this array will be used to check if a node has been visited or not 21 22 23 24 25 26 27 for(int i=0;i<7;i++) { dist[i] = INT_MAX; vis[i] = 0; par[i] = i; 28 29 30 31 priority_queue, vector > > pq; 32 33 34 vis[u] = 0; dist[u] = 0; par[u] = u; 35 36 37 pq.push({0,0}); int flap=A: 38

37 38 TERLER 39 40 . 41 pq.push({0,0}); int flag=0; while(!pq.empty()) { pair p = pq.top(); pq.pop(); int n = p.second; double d = p.first; flag =0; 42 43 E 44 45 46 47 48 49 50 51 vis[n] =1; for(int i=0;i<7; i++) { if(adj[n][i]!=0.0) { double temp = (d+adj[n][i]); if((vis[i]==0 && dist[i]>temp)) { dist[i]=(d+adj[n][i]); pq.push({dist[i],i}); 52 53 54 55 马昭四wmwww码 如归%9B%BB $5888aa66858822乃江 56 57 58 59 60 61 par[i] = n; flag=1; } } } if(flag==0) break; 62 ------ 63 64 65 } 66 67 cout<<"The shortest distance to the destination node is equal to : "««dist[v]<<"\n\n"; 68 69 vector int> path; // vector to store the shortest path from source to destination 70 71 72 while(v!=par[v]) {path.push_back(v);v=par[v];} reverse(path.begin(),path.end()); 73 74

73 reverse(path.begin(),patn.end()); 74 76 cout<<"The shortest path is : \n"; cout<"< > adj_mat(7,vector(7,0.0)); //adjacency matrix representation of the graph 83 BE 84 85 86 87 vector > arr(7); arr[@] = {256.6,92.3}; arr[1] = {120.5,5.5}; arr[2] = {350.0,165.5}; arr[3] = {120.3,10.26}; arr[4] = {40.8,72.35}; arr[5] = {92.5,86.4}; arr[6] {90.5,302.1}; 88 89 90 91 = 92 93 int u,v; 94 95 96 cout<<"enter the source and destination node\n"; cin>>u>>V; // adding the neighbours of node o to the graph adj_mat[0][1] = calc_dist(arr[@].first, arr[0].second, arr[1].first, arr[1].second); adj_mat[0][2] = calc_dist(arr[0].first, arr[@].second, arr[2].first, arr[2].second); 97 98 = = = = = = 99 100 101 // adding the neighbours of node 1 to the graph adj_mat[1][3] = calc_dist(arr[1].first, arr[1].second, arr[3].first, arr[3].second); adj_mat[1][0] = calc_dist(arr[1].first, arr[1].second, arr[@].first, arr[@].second); 102 103 104 105 // adding the neighbours of node 2 to the graph adj_mat[2][3] = calc_dist(arr[2].first, arr[2]. second, arr[3].first, arr[3].second); adj_mat[2][0] = calc_dist(arr[2].first, arr[2]. second, arr[@].first, arr[@].second); 106 107 108 109 // adding the neighbours of node 3 to the graph adj_mat[3][4] = calc_dist(arr[3].first, arr[3]. second, arr[4].first, arr[4].second); adj mat/3115] = calc dist(arr[3].first, arr[3].second, arr[5].first, arr[5].second); 110

110 111 adj_mat[3][5] = calc_dist(arr[3].first, arr[3].second, arr[5].first, arr[5].second); adj_mat[3][6] = calc_dist(arr[3].first, arr[3].second, arr[6].first, arr[6].second); adj_mat[3][1] = calc_dist(arr[3].first, arr[3]. second, arr[1].first, arr[1].second); adj_mat[3][2] = calc_dist(arr[3].first, arr[3].second, arr[2].first, arr[2].second); 112 113 114 115 116 // adding the neighbours of node 4 to the graph adj_mat[4][3] = calc_dist(arr[4].first, arr[4]. second, arr[3].first, arr[3].second); adj_mat[4][5] = calc_dist(arr[4].first, arr[4].second, arr[5].first, arr[5].second); 117 118 119 120 // adding the neighbours of node 5 to the graph adj_mat[5][4] = calc_dist(arr[5].first, arr[5].second, arr[4].first, arr[4].second); adj_mat[5][3] = calc_dist(arr[5].first, arr[5].second, arr[3].first, arr[3].second); adj_mat[5][6] = calc_dist(arr[5].first, arr[5].second, arr[6].first, arr[6].second); 121 122 123 124 // adding the neighbours of node 6 to the graph 125 126 127 adj_mat[6][5] = calc_dist(arr[6].first, arr[6].second, arr[5].first, arr[5].second); adj_mat[6][3] = calc_dist(arr[6].first, arr[6].second, arr[3].first, arr[3].second); dijkstras(adj_mat,u,v); 128 129

Output:-

enter the source and destination node 05 The shortest distance to the destination node is equal to : 247.244 The shortest path is : Cinema->Sport Center-Cafe-clothes Store

Source code:-

#include
using namespace std;
// 0. Cinema: (256.6,92.3)
// 1. Sport Center: (120.5,5.5)
// 2. Restaurant: (350.0, 165.5)
// 3. Cafe: (102.3,10.26)
// 4. Bowling: (40.8,72.35)
// 5. Clothes Store: (92.5,86.4)
// 6. Toy Store: (90.5,302.1)

// function to calculate the eucledian distance between two nodes
string pl[7] = {"Cinema","Sport Center","Restaurant","Cafe","Bowling","Clothes Store","Toy Store"};
double calc_dist(double x,double y,double x1,double y1)
{
    return sqrt(pow(x1-x,2)+pow(y1-y,2));
}

// applying dijkstras algorithm to find the shortest path from source to destination node
void dijkstras(vector > adj,int u,int v) // u is source and v is destination 
{
    double dist[7]; // this array will store the shortest distance to any node i , from the source node
    int par[7]; // this array will store the parent to a node i 
    int vis[7]; // this array will be used to check if a node has been visited or not
    
    for(int i=0;i<7;i++)
    {
        dist[i] = INT_MAX;
        vis[i] = 0;
        par[i] = i;
    }
    priority_queue, vector > > pq;

    vis[u] = 0;
    dist[u] = 0;
    par[u] = u;

    pq.push({0,0});
    int flag=0;
    while(!pq.empty())
    {
        pair p = pq.top();
        pq.pop();
        int n = p.second;
        double d = p.first;
        flag =0;

        vis[n] =1;
        for(int i=0;i<7;i++)
        {
            if(adj[n][i]!=0.0)
            {
            double temp = (d+adj[n][i]);
            if((vis[i]==0 && dist[i]>temp))
            {
                dist[i]=(d+adj[n][i]);
                pq.push({dist[i],i});

                par[i] = n;
                flag=1;
            }
            }
        }
        if(flag==0)
        break;
    }

    cout<<"The shortest distance to the destination node is equal to : "< path; // vector to store the shortest path from source to destination

    while(v!=par[v])
    {path.push_back(v);v=par[v];}
    reverse(path.begin(),path.end());

    cout<<"The shortest path is : \n";
    cout<"< > adj_mat(7,vector(7,0.0)); //adjacency matrix representation of the graph

    vector > arr(7);
    arr[0] = {256.6,92.3};
    arr[1] = {120.5,5.5};
    arr[2] = {350.0,165.5};
    arr[3] = {120.3,10.26};
    arr[4] = {40.8,72.35};
    arr[5] = {92.5,86.4};
    arr[6] = {90.5,302.1};

    int u,v;
    cout<<"enter the source and destination node\n";
    cin>>u>>v;
    // adding the neighbours of node 0 to the graph
    adj_mat[0][1] = calc_dist(arr[0].first,arr[0].second,arr[1].first,arr[1].second);
    adj_mat[0][2] = calc_dist(arr[0].first,arr[0].second,arr[2].first,arr[2].second);

    // adding the neighbours of node 1 to the graph
    adj_mat[1][3] = calc_dist(arr[1].first,arr[1].second,arr[3].first,arr[3].second);
    adj_mat[1][0] = calc_dist(arr[1].first,arr[1].second,arr[0].first,arr[0].second);

    // adding the neighbours of node 2 to the graph
    adj_mat[2][3] = calc_dist(arr[2].first,arr[2].second,arr[3].first,arr[3].second);
    adj_mat[2][0] = calc_dist(arr[2].first,arr[2].second,arr[0].first,arr[0].second);

    // adding the neighbours of node 3 to the graph
    adj_mat[3][4] = calc_dist(arr[3].first,arr[3].second,arr[4].first,arr[4].second);
    adj_mat[3][5] = calc_dist(arr[3].first,arr[3].second,arr[5].first,arr[5].second);
    adj_mat[3][6] = calc_dist(arr[3].first,arr[3].second,arr[6].first,arr[6].second);
    adj_mat[3][1] = calc_dist(arr[3].first,arr[3].second,arr[1].first,arr[1].second);
    adj_mat[3][2] = calc_dist(arr[3].first,arr[3].second,arr[2].first,arr[2].second);

    // adding the neighbours of node 4 to the graph
    adj_mat[4][3] = calc_dist(arr[4].first,arr[4].second,arr[3].first,arr[3].second);
    adj_mat[4][5] = calc_dist(arr[4].first,arr[4].second,arr[5].first,arr[5].second);

    // adding the neighbours of node 5 to the graph
    adj_mat[5][4] = calc_dist(arr[5].first,arr[5].second,arr[4].first,arr[4].second);
    adj_mat[5][3] = calc_dist(arr[5].first,arr[5].second,arr[3].first,arr[3].second);
    adj_mat[5][6] = calc_dist(arr[5].first,arr[5].second,arr[6].first,arr[6].second);

    // adding the neighbours of node 6 to the graph

    adj_mat[6][5] = calc_dist(arr[6].first,arr[6].second,arr[5].first,arr[5].second);
    adj_mat[6][3] = calc_dist(arr[6].first,arr[6].second,arr[3].first,arr[3].second);
    dijkstras(adj_mat,u,v);
}