Pretend you own your own Uber-like Taxi Service Company. “Uber-like” implies tha

Question

Pretend you own your own Uber-like Taxi Service Company. “Uber-like” implies that

you have no headquarters but rather a team of drivers that begin their taxi service

from their home (and they live all over the U.S.). These drivers must pick up their

clients and get them to the correct destination utilizing an “optimal” fast route

(not the “long” route as the real Uber does to gain the most money).

Requirements:

After receiving a call from a customer, you must determine which of your drivers is available (look for the driver closest to the customer that is being picked up). You would need to maintain a list of drivers in certain locations (hint: store them in an ADT).

Select a route for your driver (review Dijkstra’s algorithm and graph ADT).

You need an interface for this application. I prefer GUI interfaces but if you make a good text-based one, I will accept it (but you probably won’t get the points that a GUI one earns you). I am allowing you to use a GUI generator/builder if you want (I know Eclipse and Netbeans have ones and you can check out JavaFX). I am not measuring how good you are at building a GUI but rather how you build your algorithms and data structures.

Explanation / Answer

#include <stdio.h>

#include <limits.h>

#define V 4

// location repersent location of drivers and user

// suppose user is at Node A

// rest node repersent driver location

//this is demo program to find out distance of user from all drivers and choose nearest one to pickup user

int minDistance(int dist[], bool sptSet[])

{

// Initialize min value

int min = INT_MAX, min_index;

for (int v = 0; v < V; v++)

if (sptSet[v] == false && dist[v] <= min)

min = dist[v], min_index = v;

return min_index;

}

int driverDistance(int dist[], int n)

{

// 0,1,2,3 repsersent node A,B,C,D respectivily

printf("Driver | Distance from User ");

for (int i = 0; i < V; i++)

printf("%d %d ", i, dist[i]);

}

void findminPath(int location[V][V], int src)

{

int dist[V]; // dist[i] will hold the shortest

// distance from user to all driver located at i

bool visit[V];

// Initialize all driver distances as INFINITE

for (int i = 0; i < V; i++)

dist[i] = INT_MAX, visit[i] = false;

dist[src] = 0;

for (int count = 0; count < V-1; count++)

{

// Pick the minimum distance vertex from the set of vertices not

// yet processed. u is always equal to src in first iteration.

int u = minDistance(dist, visit);

// Mark the picked vertex as processed

visit[u] = true;

// Update dist value of the adjacent vertices (diver) of the picked adjacent picked driver or user.

for (int v = 0; v < V; v++)

if (!visit[v] && location[u][v] && dist[u] != INT_MAX && dist[u]+location[u][v] < dist[v])

dist[v] = dist[u] + location[u][v];

}

// print the Ditance of each driver from user

driverDistance(dist, V);

}

int main()

{

/* Let us create the example distance graph between all drivers in the city and user

B

/ |

10/ | 16

/ |

A (user)| D

5| /

| /

20 | /20

| /

C

Above Simple repersent A as USER ASN REST DRIVERS

*/

int location[V][V] = {

{0,10,20,0},

{10,0,5,16},

{20,5,0,20},

{0,16,20,0}

};

findminPath(location, 0);

return 0;

}

// in Above example Driver at location B, Will pickup user standing at Node A

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.