|
The Parallel computing has become essential for solving computationally intensive problems efficiently. Dijkstra’s algorithm is a well-known graph algorithm used to find the shortest paths from a single source vertex to all other vertices in a graph. When dealing with large graphs and it becomes necessary to parallelize the algorithm to achieve faster results.
Approaches :- Data Parallelism using OpenMP
- Task Parallelism using OpenMP
Approach 1: Data Parallelism using OpenMPDivide the nodes into chunks and assign each chunk to the thread. Each thread computes the shortest path for its assigned nodes in the parallel.
Syntax:
#include <omp.h>
#pragma omp parallel for
for (int i = 0; i < num_nodes; ++i) {
// Compute shortest path for node i
}
Below is the implementation of the algorithm:
C++
#include <iostream>
#include <vector>
#include <limits>
#include <omp.h>
#define INF std::numeric_limits<int>::max()
void GFG(const std::vector<std::vector<int>>& graph, int start) {
int num_nodes = graph.size();
std::vector<int> dist(num_nodes, INF);
std::vector<bool> visited(num_nodes, false);
dist[start] = 0;
#pragma omp parallel for
for (int i = 0; i < num_nodes; ++i) {
int u = -1, min_dist = INF;
// Find the node with the shortest distance
for (int j = 0; j < num_nodes; ++j) {
if (!visited[j] && dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
if (u == -1) break;
// Relax adjacent nodes
for (int v = 0; v < num_nodes; ++v) {
if (!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
visited[u] = true;
}
// Print the shortest distances
std::cout << "Vertex \t Distance from Source\n";
for (int i = 0; i < num_nodes; ++i) {
std::cout << i << "\t\t" << dist[i] << "\n";
}
}
int main() {
std::vector<std::vector<int>> graph = {
{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
GFG(graph, 0);
return 0;
}
import java.util.ArrayList;
import java.util.Arrays;
public class DijkstraAlgorithm {
static final int INF = Integer.MAX_VALUE;
static void dijkstra(ArrayList<ArrayList<Integer>> graph, int start) {
int numNodes = graph.size();
int[] dist = new int[numNodes];
boolean[] visited = new boolean[numNodes];
Arrays.fill(dist, INF);
dist[start] = 0;
for (int count = 0; count < numNodes - 1; count++) {
int u = -1, minDist = INF;
// Find the vertex with the minimum distance
for (int v = 0; v < numNodes; v++) {
if (!visited[v] && dist[v] < minDist) {
u = v;
minDist = dist[v];
}
}
if (u == -1) break;
visited[u] = true;
// Update distances for adjacent vertices
for (int v = 0; v < numNodes; v++) {
if (!visited[v] && graph.get(u).get(v) != 0 &&
dist[u] != INF && dist[u] + graph.get(u).get(v) < dist[v]) {
dist[v] = dist[u] + graph.get(u).get(v);
}
}
}
// Print the shortest distances
System.out.println("Vertex \t Distance from Source");
for (int i = 0; i < numNodes; i++) {
System.out.println(i + "\t\t" + dist[i]);
}
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> graph = new ArrayList<>(Arrays.asList(
new ArrayList<>(Arrays.asList(0, 4, 0, 0, 0, 0, 0, 8, 0)),
new ArrayList<>(Arrays.asList(4, 0, 8, 0, 0, 0, 0, 11, 0)),
new ArrayList<>(Arrays.asList(0, 8, 0, 7, 0, 4, 0, 0, 2)),
new ArrayList<>(Arrays.asList(0, 0, 7, 0, 9, 14, 0, 0, 0)),
new ArrayList<>(Arrays.asList(0, 0, 0, 9, 0, 10, 0, 0, 0)),
new ArrayList<>(Arrays.asList(0, 0, 4, 14, 10, 0, 2, 0, 0)),
new ArrayList<>(Arrays.asList(0, 0, 0, 0, 0, 2, 0, 1, 6)),
new ArrayList<>(Arrays.asList(8, 11, 0, 0, 0, 0, 1, 0, 7)),
new ArrayList<>(Arrays.asList(0, 0, 2, 0, 0, 0, 6, 7, 0))
));
dijkstra(graph, 0);
}
}
// This code is contributed by shivamgupta0987654321
import sys
from typing import List
# Define infinity as a large enough integer. This will represent
#the maximum possible distance in the graph.
INF = sys.maxsize
def GFG(graph: List[List[int]], start: int):
num_nodes = len(graph)
dist = [INF] * num_nodes
visited = [False] * num_nodes
dist[start] = 0
for _ in range(num_nodes):
u = -1
min_dist = INF
# Find the node with the shortest distance
for j in range(num_nodes):
if not visited[j] and dist[j] < min_dist:
u = j
min_dist = dist[j]
if u == -1:
break
# Relax adjacent nodes
for v in range(num_nodes):
if not visited[v] and graph[u][v] and dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
visited[u] = True
# Print the shortest distances
print("Vertex \t Distance from Source")
for i in range(num_nodes):
print(f"{i} \t\t {dist[i]}")
def main():
graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
GFG(graph, 0)
if __name__ == "__main__":
main()
function dijkstra(graph, start) {
const INF = Number.MAX_SAFE_INTEGER;
const numNodes = graph.length;
const dist = new Array(numNodes).fill(INF);
const visited = new Array(numNodes).fill(false);
dist[start] = 0;
for (let count = 0; count < numNodes - 1; count++) {
let u = -1, minDist = INF;
// Find the vertex with the minimum distance
for (let v = 0; v < numNodes; v++) {
if (!visited[v] && dist[v] < minDist) {
u = v;
minDist = dist[v];
}
}
if (u === -1) break;
visited[u] = true;
// Update distances for adjacent vertices
for (let v = 0; v < numNodes; v++) {
if (!visited[v] && graph[u][v] !== 0 &&
dist[u] !== INF && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
}
// Print the shortest distances
console.log("Vertex \t Distance from Source");
for (let i = 0; i < numNodes; i++) {
console.log(i + "\t\t" + dist[i]);
}
}
// Driver code
const graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
];
dijkstra(graph, 0);
OutputVertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
Approach 2: Task Parallelism using OpenMPCreate parallel tasks for the each node. Each task computes the shortest path for its assigned node independently.
Syntax:
#include <omp.h>
#pragma omp parallel
{
#pragma omp single nowait
{
for (int i = 0; i < num_nodes; ++i) {
#pragma omp task
{
// Compute shortest path for node i
}
}
}
}
Implementation :
C++
#include <iostream>
#include <limits>
#include <omp.h>
#include <vector>
#define INF std::numeric_limits<int>::max()
void GFG(const std::vector<std::vector<int> >& graph,
int start)
{
int num_nodes = graph.size();
std::vector<int> dist(num_nodes, INF);
std::vector<bool> visited(num_nodes, false);
dist[start] = 0;
#pragma omp parallel
{
#pragma omp single nowait
{
for (int i = 0; i < num_nodes; ++i) {
#pragma omp task
{
int u = -1, min_dist = INF;
// Find the node with shortest distance
for (int j = 0; j < num_nodes; ++j) {
if (!visited[j]
&& dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
if (u != -1) {
// The Relax adjacent nodes
for (int v = 0; v < num_nodes;
++v) {
if (!visited[v] && graph[u][v]
&& dist[u] + graph[u][v]
< dist[v]) {
dist[v]
= dist[u] + graph[u][v];
}
}
visited[u] = true;
}
}
}
}
}
// Print the shortest distances
std::cout << "Vertex \t Distance from Source\n";
for (int i = 0; i < num_nodes; ++i) {
std::cout << i << "\t\t" << dist[i] << "\n";
}
}
int main()
{
std::vector<std::vector<int> > graph
= { { 0, 4, 0, 0, 0, 0, 0, 8, 0 },
{ 4, 0, 8, 0, 0, 0, 0, 11, 0 },
{ 0, 8, 0, 7, 0, 4, 0, 0, 2 },
{ 0, 0, 7, 0, 9, 14, 0, 0, 0 },
{ 0, 0, 0, 9, 0, 10, 0, 0, 0 },
{ 0, 0, 4, 14, 10, 0, 2, 0, 0 },
{ 0, 0, 0, 0, 0, 2, 0, 1, 6 },
{ 8, 11, 0, 0, 0, 0, 1, 0, 7 },
{ 0, 0, 2, 0, 0, 0, 6, 7, 0 } };
GFG(graph, 0);
return 0;
}
import java.util.Arrays;
import java.util.List;
public class ShortestPath {
// Define a constant for infinity value as there's no
// direct equivalent in Java as in C++.
private static final int INF = Integer.MAX_VALUE;
public static void
computePaths(List<List<Integer> > graph, int start)
{
int numNodes = graph.size();
int[] dist
= new int[numNodes]; // Distance array to store
// the shortest path to
// each vertex
boolean[] visited
= new boolean[numNodes]; // Boolean array to
// track visited
// vertices
Arrays.fill(
dist,
INF); // Initialize all distances to infinity
dist[start] = 0; // Distance from the start vertex
// to itself is always 0
// Loop to find shortest path for all vertices
for (int i = 0; i < numNodes; ++i) {
int u = -1;
int minDist = INF;
// Find the unvisited vertex with the shortest
// distance from the source
for (int j = 0; j < numNodes; ++j) {
if (!visited[j] && dist[j] < minDist) {
u = j;
minDist = dist[j];
}
}
// If no vertex is found (u remains -1),
// continue to the next iteration
if (u == -1)
continue;
// Visit the vertex with the shortest distance
// found in this iteration
for (int v = 0; v < numNodes; ++v) {
// Relax the edge if a shorter path through
// u is found
if (!visited[v] && graph.get(u).get(v) != 0
&& dist[u] + graph.get(u).get(v)
< dist[v]) {
dist[v] = dist[u] + graph.get(u).get(v);
}
}
// Mark the current node as visited
visited[u] = true;
}
// Print the shortest distances from the source to
// each vertex
System.out.println(
"Vertex \t Distance from Source");
for (int i = 0; i < numNodes; ++i) {
System.out.println(
i + "\t\t"
+ (dist[i] == INF ? "Infinity" : dist[i]));
}
}
public static void main(String[] args)
{
// Graph represented as an adjacency matrix
List<List<Integer> > graph = Arrays.asList(
Arrays.asList(0, 4, 0, 0, 0, 0, 0, 8, 0),
Arrays.asList(4, 0, 8, 0, 0, 0, 0, 11, 0),
Arrays.asList(0, 8, 0, 7, 0, 4, 0, 0, 2),
Arrays.asList(0, 0, 7, 0, 9, 14, 0, 0, 0),
Arrays.asList(0, 0, 0, 9, 0, 10, 0, 0, 0),
Arrays.asList(0, 0, 4, 14, 10, 0, 2, 0, 0),
Arrays.asList(0, 0, 0, 0, 0, 2, 0, 1, 6),
Arrays.asList(8, 11, 0, 0, 0, 0, 1, 0, 7),
Arrays.asList(0, 0, 2, 0, 0, 0, 6, 7, 0));
// Call the function to compute the shortest paths
// from vertex 0
computePaths(graph, 0);
}
}
import numpy as np
def GFG(graph, start):
num_nodes = len(graph)
dist = [float('inf')] * num_nodes
visited = [False] * num_nodes
dist[start] = 0
for _ in range(num_nodes):
u = -1
min_dist = float('inf')
# Find the node with shortest distance
for j in range(num_nodes):
if not visited[j] and dist[j] < min_dist:
u = j
min_dist = dist[j]
if u != -1:
# Relax adjacent nodes
for v in range(num_nodes):
if not visited[v] and graph[u][v] and dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
visited[u] = True
# Print the shortest distances
print("Vertex \t Distance from Source")
for i in range(num_nodes):
print(i, "\t\t", dist[i])
if __name__ == "__main__":
graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
GFG(graph, 0)
# This code is contributed by Ayush Mishra
const INF = Number.MAX_SAFE_INTEGER;
function GFG(graph, start) {
const num_nodes = graph.length;
const dist = new Array(num_nodes).fill(INF);
const visited = new Array(num_nodes).fill(false);
dist[start] = 0;
for (let i = 0; i < num_nodes; ++i) {
let u = -1, min_dist = INF;
// Find the node with shortest distance
for (let j = 0; j < num_nodes; ++j) {
if (!visited[j] && dist[j] < min_dist) {
u = j;
min_dist = dist[j];
}
}
if (u !== -1) {
// Relax adjacent nodes
for (let v = 0; v < num_nodes; ++v) {
if (!visited[v] && graph[u][v] && dist[u] + graph[u][v] < dist[v]) {
dist[v] = dist[u] + graph[u][v];
}
}
visited[u] = true;
}
}
// Print the shortest distances
console.log("Vertex \t Distance from Source");
for (let i = 0; i < num_nodes; ++i) {
console.log(i + "\t\t" + dist[i]);
}
}
const graph = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
];
GFG(graph, 0);
OutputVertex Distance from Source
0 0
1 4
2 12
3 19
4 21
5 11
6 9
7 8
8 14
|
