Scribd
Upload
32 views5 pages

Dijkstra's (SSSP)

The document outlines Dijkstra's algorithm for finding the shortest path from a single source in a graph. It includes a detailed algorithm description, source code in C, and an analysis of time and space complexity. The algorithm is implemented to calculate the shortest distances from a warehouse to various delivery points and the total minimum distance for delivering packages and returning.

Uploaded by

santanujanacse2023
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
32 views5 pages

Dijkstra's (SSSP)

The document outlines Dijkstra's algorithm for finding the shortest path from a single source in a graph. It includes a detailed algorithm description, source code in C, and an analysis of time and space complexity. The algorithm is implemented to calculate the shortest distances from a warehouse to various delivery points and the total minimum distance for delivering packages and returning.

Uploaded by

santanujanacse2023
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Algorithm(Dijkstra’s Single Source Shortest Path):

Algorithm dijkstra(graph[V][V], src, dist[V])

1. Initialize an array sptSet[V] to 0 for all vertices


2. Set all distances in dist[V] to INF
3. Set dist[src] = 0

4. Repeat V-1 times:


a. u = minDistance(dist, sptSet)
b. Set sptSet[u] = 1

c. For each vertex v from 0 to V-1:


i. If v is not in sptSet AND there is an edge from u to v
ii. AND dist[u] is not INF
iii. AND (dist[u] + graph[u][v]) < dist[v]
then update dist[v] = dist[u] + graph[u][v]

End
Source Code:

#include <stdio.h>
#include <limits.h>

#define V 8
#define INF 99999

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

int min = INF, min_index;


for (int v = 0; v < V; v++)
if (!sptSet[v] && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}

void dijkstra(int graph[V][V], int src, int dist[]) {


int sptSet[V];
for (int i = 0; i < V; i++) {
dist[i] = INF;
sptSet[i] = 0;
}
dist[src] = 0;
for (int count = 0; count < V - 1; count++) {
int u = minDistance(dist, sptSet);
sptSet[u] = 1;

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


if (!sptSet[v] && graph[u][v] && dist[u] != INF &&
dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
}

int main() {
int graph[V][V] = {
{0, 40, 60, 45, 0, 0, 0, 0},
{40, 0, 0, 0, 100, 0, 0, 0},
{60, 0, 0, 40, 0, 0, 80, 70},
{45, 30, 40, 0, 60, 0, 50, 0},
{0, 100, 0, 60, 0, 50, 30, 0},
{0, 0, 0, 0, 50, 0, 30, 70},
{0, 0, 80, 50, 30, 30, 0, 40},
{0, 0, 70, 0, 0, 70, 40, 0},
};

int dist[V];
dijkstra(graph, 0, dist);

printf("Shortest distances from C1 (Warehouse) to all other points:\n");

printf(" Delivery Point Distance from C1 (Warehouse) \n");

for (int i = 1; i < V; i++) {


printf(" C%d -> %d \n", i + 1, dist[i]);
}
int deliveryPoints[] = {1, 2, 3,4, 5, 6, 7};
int n = sizeof(deliveryPoints) / sizeof(deliveryPoints[0]);

int totalDistance = 0;

for (int i = 0; i < n; i++) {


int dist[V];
dijkstra(graph, 0, dist);
totalDistance += dist[deliveryPoints[i]];

dijkstra(graph, deliveryPoints[i], dist);


totalDistance += dist[0];
}

printf("Total minimum distance to deliver all packages and return: %d\n", totalDistance);

return 0;
}
Input/Output:

Analysis:
Time Complexity:
• Best Case: O(V²)
• Worst Case: O(V²)

With Min-Heap (Adjacency List):


• Best Case: O((V + E) log V)
• Worst Case: O((V + E) log V)

Space Complexity:
• Best Case: O(V²)
• Worst Case: O(V²)
(For adjacency matrix)
With Adjacency List:
• Best Case: O(V + E)
• Worst Case: O(V + E)

You might also like