6

Implement a parallel programming task using graphs

 9 months ago
source link: https://www.geeksforgeeks.org/implement-a-parallel-programming-task-using-graphs/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Implement a parallel programming task using graphs

Discuss
Courses
Practice

Given a weighted directed graph with N nodes and M edges along with a source node S, useParallel Programming to find the shortest distance from the source node S to all other nodes in the graph. The graph is given as an edge list edges[][] where for each index i, there is an edge from edges[i][0] to edges[i][1] with weight edges[i][2].

Example:

Input: N = 5, M = 8, S = 0, edges = {{0, 1, 2}, {0, 2, 4}, {1, 2, 1}, {1, 3, 7}, {2, 3, 3}, {2, 4, 5}, {3, 4, 2}, {4, 0, 6}}

Output: Shortest Distances from Vertex 0:
Vertex 0: 0, Vertex 1: 2, Vertex 2: 3, Vertex 3: 6, Vertex 4: 8

Approach:

This problem is typically solved using Dijkstra’s algorithm for a sequential solution. However, the task is to parallelize this algorithm effectively to exploit the power of parallel computing. Below is the implementation for the above approach

Below is the implementation:

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int V;
vector<vector<pair<int, int> > > adj;
void addEdge(int u, int v, int w)
{
adj[u].push_back({ v, w });
}
void sequentialDijkstra(int src, vector<int>& dist)
{
// Initialize all the distance as infinite
dist.assign(V, INF);
dist[src] = 0;
// Create a set to store vertices with the minimum
// distance
vector<bool> processed(V, false);
// record the start time
auto start_time = chrono::high_resolution_clock::now();
// Find shortest path for all vertices
for (int count = 0; count < V - 1; ++count) {
int u = -1;
for (int i = 0; i < V; ++i) {
if (!processed[i]
&& (u == -1 || dist[i] < dist[u]))
u = i;
}
// Mark the picked vertex as processed
processed[u] = true;
// Update dist value of the adjacent vertices of the
// picked vertex.
for (const auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (!processed[v] && dist[u] != INF
&& dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
}
}
}
// record the end time
auto end_time = chrono::high_resolution_clock::now();
auto duration
= chrono::duration_cast<chrono::microseconds>(
end_time - start_time);
// Print the sequential execution time
cout << "Sequential Dijkstra Execution Time: "
<< duration.count() << " microseconds" << endl;
}
void parallelDijkstra(int src, vector<int>& dist)
{
dist.assign(V, INF);
dist[src] = 0;
// Create a set to store vertices with the minimum
// distance
vector<bool> processed(V, false);
// Record the start time
auto start_time = chrono::high_resolution_clock::now();
// Find shortest path for all vertices
for (int count = 0; count < V - 1; ++count) {
int u = -1;
#pragma omp parallel for
for (int i = 0; i < V; ++i) {
if (!processed[i]
&& (u == -1 || dist[i] < dist[u]))
#pragma omp critical
u = (u == -1 || dist[i] < dist[u]) ? i : u;
}
// Mark the picked vertex as processed
processed[u] = true;
// Update dist value of the adjacent vertices of the
// picked vertex using Parallel Programming
#pragma omp parallel for
for (const auto& edge : adj[u]) {
int v = edge.first;
int w = edge.second;
if (!processed[v] && dist[u] != INF
&& dist[u] + w < dist[v]) {
#pragma omp critical
if (dist[u] != INF && dist[u] + w < dist[v])
dist[v] = dist[u] + w;
}
}
}
// Record the end time
auto end_time = chrono::high_resolution_clock::now();
auto duration
= chrono::duration_cast<chrono::microseconds>(
end_time - start_time);
// Print the parallel execution time
cout << "Parallel Dijkstra Execution Time: "
<< duration.count() << " microseconds"
<< "\n";
}
int main()
{
int S = 0;
V = 5;
adj.resize(V);
addEdge(0, 1, 2);
addEdge(0, 2, 4);
addEdge(1, 2, 1);
addEdge(1, 3, 7);
addEdge(2, 3, 3);
addEdge(3, 4, 5);
addEdge(3, 4, 2);
addEdge(4, 0, 6);
vector<int> dist(V, 1e9);
sequentialDijkstra(S, dist);
parallelDijkstra(S, dist);
cout << "Shortest distances from Vertex " << S << ":\n";
for (int i = 0; i < V; ++i) {
cout << "Vertex " << i << ": " << dist[i];
if (i != V - 1)
cout << ", ";
}
return 0;
}
Output 
Sequential Dijkstra Execution Time: 2 microseconds
Parallel Dijkstra Execution Time: 1 microseconds
Shortest distances from Vertex 0:
Vertex 0: 0, Vertex 1: 2, Vertex 2: 3, Vertex 3: 6, Vertex 4: 8

The time difference between parallel implementation and sequential implementation of graphs is 1 microsecond.

Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!

Recommended Problems
Frequently asked DSA Problems
Last Updated : 13 Dec, 2023
Like Article
Save Article

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK