School of Computing

SRM IST, Kattankulathur – 603 203

Course Code: 18CSC204J

Course Name: DESIGN AND ANALYSIS OF ALGORITHMS

Problem Statement ROUTE SELECTION FOR ONLINE FOOD DELIVERY SYSTEM

Name of the candidate M. ARAVINDH RAAM

Team Members S. PAVIN

Date of submission 28.04.2023

Mark Split Up
S. No Description Maximum Mark Mark Obtained

1 Exercise 5

2 Viva 5

Total 10

Staff Signature with date

SRM INSTITUTE OF SCIENCE AND TECHNOLOGY
KATTANKULATHUR — 603 203
BONAFIDE CERTIFICATE

Certified that this project report “Route selection for online food delivery
system” is the bonafide work of

Aravindh Raam M (RA2111031010078) ,Pavin S (RA2111031010087) who

carried out the project work under my

supervision.

SIGNATURE SIGNATURE

Dr. M. Jeyaselvi Dr. Annapurani Panaiyappan K

Assistant Professor Head of the Department
Networking and Communications Networking and Communications
SRM Institute of Science and Technology SRM Institute of Science and Technology
Kattankulathur Kattankulathur
 DIJKSTRA ALGORITHM
Dijkstra's Algorithm was conceived by computer scientist Edsger W. Dijkstra in
1956.
It is a single source shortest paths algorithm. It means that it finds the shortest
paths from a single source vertex to all other vertices in a graph.
It is a greedy algorithm and works for both directed and undirected, positively
weighted graphs (a graph is called positively weighted if all of its edges have
only positive weights).
DESIGN APPROACH : Greedy Algorithm
Algorithm:
Mark the source node with a current distance of 0 and the rest with infinity.
Set the non-visited node with the smallest current distance as the current node,
lets say C.
For each neighbour N of the current node C: add the current distance of C with
the weight of the edge connecting C-N. If it is smaller than the current distance
of N, set it as the new current distance of N.
Mark the current node C as visited.
Go to step 2 if there are any nodes are unvisited.
The final paths we get are:
A=0(source)
B=4(A−>B)
C=5(A−>C)
D=13(A−>B−>8
E=8(A−>C−>E)
F=14!(A−>C−>E−>F)

IMPLEMENTATION USING C++:

#include <iostream>
using namespace std;
#include <limits.h>

#define V 6 // Number of vertices in the graph

//Function to find the vertex with minimum distance

int minDist(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;
}
//Function to print the constructed distance array
void printSolution(int distance[])
{
cout <<"Vertex \t Distance from Source" << endl;
for (int i = 0; i < V; i++)
cout << (char)(i+65) << " \t\t"<<distance[i]<< endl;
}

// Function that implements Dijkstra's algorithm

void dijkstra(int graph[V][V], int src)
{
int distance[V]; //inititalizing output array

bool sptSet[V]; // list of visisted nodes

// Initializing all distances as INFINITE and stpSet[] as false

for (int i = 0; i < V; i++)
distance[i] = INT_MAX, sptSet[i] = false;

// Setting distance of source as 0

distance[src] = 0;

// Find shortest path for all vertices

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

//calling minDistance to pick next vertex

int u = minDist(distance, sptSet);
 // Mark the picked vertex as visited
sptSet[u] = true;

//Relaxing all neighbours of U

for (int v = 0; v < V; v++)
{
if (!sptSet[v] && graph[u][v] && distance[u] != INT_MAX
&& dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}

// print the constructed distance array

printSolution(dist);
}

// driver function
int main()
{

//Example graph
//Same as Graph in example diagram above

int graph[V][V] = { {0,4,5,0,0,0},

{4,0,11,9,7,0},
{5,11,0,0,3,0},
{0,9,0,0,13,2},
{0,7,3,13,0,6},
 {0,0,0,2,6,0}};
int source=0;
dijkstra(graph, source);

return 0;
}
OUTPUT:
Vertex Distance from Source
A 0
B 4
C 5
D 13
E 8
F 14
With this implementation, the time to visit each vertex becomes O(V+E) and the
time required to process all the neighbours of a vertex becomes O(logV).
Time for visiting all vertices =O(V+E)
Time required for processing one vertex=O(logV)
Time required for visiting and processing all the vertices
=O(V+E)∗O(logV)=O((V+E)logV)

BELLMAN-FORD ALGORITHM
Like other Dynamic Programming Problems, the algorithm calculates the
shortest paths in a bottom-up manner. It first calculates the shortest distances
which have at most one edge in the path. Then, it calculates the shortest paths
with at-most 2 edges, and so on. After the i-th iteration of the outer loop, the
shortest paths with at most i edges are calculated. There can be maximum |V| –
1 edges in any simple path, that is why the outer loop runs |v| – 1 times. The
idea is, assuming that there is no negative weight cycle if we have calculated
shortest paths with at most i edges, then an iteration over all edges guarantees to
give the shortest path with at-most (i+1) edges

Bellman Ford algorithm works by overestimating the length of the path from the
starting vertex to all other vertices. Then it iteratively relaxes those estimates by
finding new paths that are shorter than the previously overestimated paths.C
DESIGN APPROACH: DYNAMIC PROGRAMMING
ALGORITHM:
1. Start with the weighted graph
2. Choose a starting vertex and assign infinity path values to all the other
vertices
3. Visit each edge and relax the path distances if they are inaccurate
4. We need to do this v times because the worst case, a vertex’s path length
might need to be readjusted v times
5. Notice how the vertex at the top right corner had its path length adjusted
6. after all the vertices has their path length we check if a negative cycle is
present

IMPLEMENTATION:
#include <bits/stdc++.h>

// Struct for the edges of the graph

struct Edge {
 int u; //start vertex of the edge
int v; //end vertex of the edge
int w; //w of the edge (u,v)
};

// Graph - it consists of edges

struct Graph {
int V; // Total number of vertices in the graph
int E; // Total number of edges in the graph
struct Edge* edge; // Array of edges
};

// Creates a graph with V vertices and E edges

struct Graph* createGraph(int V, int E) {
struct Graph* graph = new Graph;
graph->V = V; // Total Vertices
graph->E = E; // Total edges

// Array of edges for graph

graph->edge = new Edge[E];
return graph;
}

// Printing the solution

void printArr(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
 }
printf("\n");
}

void BellmanFord(struct Graph* graph, int u) {

int V = graph->V;
int E = graph->E;
int dist[V];

// Step 1: fill the distance array and predecessor array

for (int i = 0; i < V; i++)
dist[i] = INT_MAX;

// Mark the source vertex

dist[u] = 0;

// Step 2: relax edges |V| - 1 times

for (int i = 1; i <= V - 1; i++) {
for (int j = 0; j < E; j++) {
// Get the edge data
int u = graph->edge[j].u;
int v = graph->edge[j].v;
int w = graph->edge[j].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
 // Step 3: detect negative cycle
// if value changes then we have a negative cycle in the graph
// and we cannot find the shortest distances
for (int i = 0; i < E; i++) {
int u = graph->edge[i].u;
int v = graph->edge[i].v;
int w = graph->edge[i].w;
if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {
printf("Graph contains negative w cycle");
return;
}
}

// No negative weight cycle found!

// Print the distance and predecessor array
printArr(dist, V);

return;
}

int main() {
// Create a graph
int V = 5; // Total vertices
int E = 8; // Total edges

// Array of edges for graph

struct Graph* graph = createGraph(V, E);
edge 0 --> 1
graph->edge[0].u = 0;
graph->edge[0].v = 1;
graph->edge[0].w = 5;

//edge 0 --> 2
graph->edge[1].u = 0;
graph->edge[1].v = 2;
graph->edge[1].w = 4;

//edge 1 --> 3
graph->edge[2].u = 1;
graph->edge[2].v = 3;
graph->edge[2].w = 3;

//edge 2 --> 1
graph->edge[3].u = 2;
graph->edge[3].v = 1;
graph->edge[3].w = 6;

//edge 3 --> 2
graph->edge[4].u = 3;
graph->edge[4].v = 2;
graph->edge[4].w = 2;

BellmanFord(graph, 0); //0 is the source vertex

 return 0;
}
Time Complexity

Best Case Complexity O(E)

Average Case Complexity O(VE)

Worst Case Complexity O(VE)

Bellman Ford vs Dijkstra

Bellman Ford's algorithm and Dijkstra's algorithm are very similar in structure.
While Dijkstra looks only to the immediate neighbors of a vertex, Bellman goes
through each edge in every iteration.
 Floyd-Warshall Algorithm
Floyd-Warshall Algorithm is an algorithm for finding the shortest path between
all the pairs of vertices in a weighted graph. This algorithm works for both the
directed and undirected weighted graphs. But, it does not work for the graphs
with negative cycles (where the sum of the edges in a cycle is negative).

ALGORITHM:
n = no of vertices
A = matrix of dimension n*n
for k = 1 to n
for i = 1 to n
for j = 1 to n
Ak[i, j] = min (Ak-1[i, j], Ak-1[i, k] + Ak-1[k, j])
return A

IMPLEMENTATION:
#include <iostream>
using namespace std;

// defining the number of vertices

#define nV 4

#define INF 999

void printMatrix(int matrix[][nV]);

// Implementing floyd warshall algorithm

void floydWarshall(int graph[][nV]) {
int matrix[nV][nV], i, j, k;

for (i = 0; i < nV; i++)

for (j = 0; j < nV; j++)
matrix[i][j] = graph[i][j];

// Adding vertices individually

for (k = 0; k < nV; k++) {
for (i = 0; i < nV; i++) {
for (j = 0; j < nV; j++) {
if (matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j];
}
}
}
printMatrix(matrix);
}

void printMatrix(int matrix[][nV]) {

for (int i = 0; i < nV; i++) {
for (int j = 0; j < nV; j++) {
if (matrix[i][j] == INF)
printf("%4s", "INF");
else
printf("%4d", matrix[i][j]);
}
printf("\n");
}
}

int main() {
int graph[nV][nV] = {{0, 3, INF, 5},
{2, 0, INF, 4},
{INF, 1, 0, INF},
{INF, INF, 2, 0}};
floydWarshall(graph);
}
Time Complexity
There are three loops. Each loop has constant complexities. So, the time
complexity of the Floyd-Warshall algorithm is O(n3).
BEST SUITED TECHNIQUE: DIJKSTRA’S ALGORITHM
REASON:

Dijkstra's algorithm is better suited for the selection of routes for online food
delivery over Floyd Warshall and Bellman-Ford algorithms for the following
reasons:

1. Efficiency: Dijkstra's algorithm is more efficient than Floyd Warshall and

Bellman-Ford algorithms for finding the shortest path between two points in a
graph. This is especially important for online food delivery, where customers
expect their orders to be delivered quickly.

2. Scalability: Dijkstra's algorithm is more scalable than Floyd Warshall and

Bellman-Ford algorithms, as it can handle larger graphs more efficiently. This is
important for online food delivery, as there may be many restaurants and
customers to consider when selecting a route.

3. Limited scope: Dijkstra's algorithm only considers the shortest path from a
single source to all other nodes in the graph, whereas Floyd Warshall and
Bellman-Ford algorithms consider the shortest path between all pairs of nodes.
This limited scope is sufficient for online food delivery, as only one source (the
restaurant) and many destinations (the customers) need to be considered.

4. Edge weights: Dijkstra's algorithm works well with non-negative edge

weights, which is often the case for distance or time-based metrics. In
comparison, Floyd Warshall and Bellman-Ford algorithms can handle negative
edge weights, but this is not as relevant for online food delivery, where the
routes are typically based on distance or time.
5. Time complexity:

Dijkstra’s algorithm O((V+E) log V)

Bellman’s Ford algorithm O(V^3)
Floyd Warshall algorithm O(VE)

In terms of time complexity, Dijkstra's algorithm is more efficient than Floyd

Warshall algorithm, as it has a lower order of complexity. However,
Bellman-Ford algorithm has a similar time complexity to Dijkstra's algorithm,
but it may require more iterations in some cases. Overall, Dijkstra's algorithm is
the best choice for online food delivery due to its efficiency and scalability, as
discussed earlier.

CONCLUSION:
Overall, Dijkstra's algorithm is the better choice for selecting routes for online
food delivery due to its efficiency, scalability, limited scope, and compatibility
with distance or time-based metrics.