Data Structures & Algorithms – Graph algorithms (e.g. Dijkstra’s shortest path, Prim’s minimum spanning tree)
Graph algorithms are a set of methods and techniques used to solve problems related to graphs, which are mathematical structures used to model pairwise relations between objects.
Two of the most well-known and widely used graph algorithms are Dijkstra’s shortest path algorithm and Prim’s minimum spanning tree algorithm.
Dijkstra’s shortest path algorithm is an algorithm for finding the shortest path between nodes in a graph, where the edge weights are non-negative. It works by relaxing the edges of the graph one by one, where relaxing an edge means updating the distance to a node if a shorter path is found. The basic idea is to start from the source node, and repeatedly select the node with the smallest distance, mark it as visited and update the distances of its adjacent nodes. The time complexity of Dijkstra’s shortest path algorithm is O(E log V) where E is the number of edges and V is the number of vertices.
Here is an example of Dijkstra’s shortest path algorithm implemented in Python:
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
heap = [(0, start)]
while heap:
current_distance, current_vertex = heapq.heappop(heap)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(heap, (distance, neighbor))
return distances
graph = {
'A': {'B': 2, 'C': 3},
'B': {'A': 2, 'D': 4, 'E': 5},
'C': {'A': 3, 'F': 1},
'D': {'B': 4, 'G': 2},
'E': {'B': 5},
'F': {'C': 1, 'G': 3},
'G': {'D': 2, 'F': 3},
}
print(dijkstra(graph, 'A'))
Prim’s minimum spanning tree algorithm is an algorithm for finding a minimum spanning tree in a weighted, connected and undirected graph. It works by growing a single tree from a starting node, adding edges in increasing order of weight, until all the vertices are in the tree. The basic idea is to start with an empty tree, and repeatedly add the vertex with the smallest edge to the tree, while ensuring that the tree remains connected. The time complexity of Prim’s minimum spanning tree algorithm is O(E log V) where E is the number of edges and V is the number of vertices. Here is an example of Prim’s minimum spanning tree algorithm implemented in Python:
def prim(graph):
minimum_spanning_tree = set()
visited = set()
heap = []
for vertex in graph:
for neighbor, weight in graph[vertex].items():
heapq.heappush(heap, (weight, vertex, neighbor))
start_vertex = next(iter(graph))
visited.add(start_vertex)
while heap:
weight, v1, v2 = heapq.heappop(heap)
if v2 not in visited:
visited.add(v2)
minimum_spanning_tree.add((v1, v2, weight))
if v1 not in visited:
visited.add(v1)
minimum_spanning_tree.add((v2, v1, weight))
return minimum_spanning_tree
graph = {
'A': {'B': 2, 'C': 3},
'B': {'A': 2, 'D': 4, 'E': 5},
'C': {'A': 3, 'F': 1},
'D': {'B': 4, 'G': 2},
'E': {'B': 5},'F': {'C': 1, 'G': 3},
'G': {'D': 2, 'F': 3},
}
print(prim(graph))
Here is an example of Dijkstra’s shortest path algorithm implemented in JavaScript:
function dijkstra(graph, start) {
let distances = {};
for (let vertex in graph) {
distances[vertex] = Infinity;
}
distances[start] = 0;
let heap = [[0, start]];
while (heap.length) {
let current = heap.shift();
let currentDistance = current[0];
let currentVertex = current[1];
if (currentDistance > distances[currentVertex]) continue;
for (let neighbor in graph[currentVertex]) {
let distance = currentDistance + graph[currentVertex][neighbor];
if (distance < distances[neighbor]) {
distances[neighbor] = distance;
heap.push([distance, neighbor]);
}
}
}
return distances;
}
let graph = {
A: { B: 2, C: 3 },
B: { A: 2, D: 4, E: 5 },
C: { A: 3, F: 1 },
D: { B: 4, G: 2 },
E: { B: 5 },
F: { C: 1, G: 3 },
G: { D: 2, F: 3 }
};
console.log(dijkstra(graph, 'A'));
Here is an example of Prim’s minimum spanning tree algorithm implemented in JavaScript:
function prim(graph) {
let minimumSpanningTree = new Set();
let visited = new Set();
let heap = [];
for (let vertex in graph) {
for (let neighbor in graph[vertex]) {
heap.push([graph[vertex][neighbor], vertex, neighbor]);
}
}
heap.sort((a, b) => a[0] - b[0]);
let startVertex = Object.keys(graph)[0];
visited.add(startVertex);
while (heap.length) {
let edge = heap.shift();
let weight = edge[0];
let v1 = edge[1];
let v2 = edge[2];
if (!visited.has(v2)) {
visited.add(v2);
minimumSpanningTree.add([v1, v2, weight]);
}
if (!visited.has(v1)) {
visited.add(v1);
minimumSpanningTree.add([v2, v1, weight]);
}
}
return minimumSpanningTree;
}
let graph = {
A: { B: 2, C: 3 },
B: { A: 2, D: 4, E: 5},
C: { A: 3, F: 1 },
D: { B: 4, G: 2 },
E: { B: 5 },
F: { C: 1, G: 3 },
G: { D: 2, F: 3 }
};
console.log(prim(graph));
Here is an example of Dijkstra’s shortest path algorithm implemented in Java:
import java.util.*;
class Dijkstra {
public static Map<String, Integer> dijkstra(Map<String, Map<String, Integer>> graph, String start) {
Map<String, Integer> distances = new HashMap<>();
for (String vertex : graph.keySet()) {
distances.put(vertex, Integer.MAX_VALUE);
}
distances.put(start, 0);
PriorityQueue<Pair> heap = new PriorityQueue<>((a, b) -> a.distance - b.distance);
heap.offer(new Pair(0, start));
while (!heap.isEmpty()) {
Pair current = heap.poll();
int currentDistance = current.distance;
String currentVertex = current.vertex;
if (currentDistance > distances.get(currentVertex)) continue;
for (String neighbor : graph.get(currentVertex).keySet()) {
int distance = currentDistance + graph.get(currentVertex).get(neighbor);
if (distance < distances.get(neighbor)) {
distances.put(neighbor, distance);
heap.offer(new Pair(distance, neighbor));
}
}
}
return distances;
}
public static void main(String[] args) {
Map<String, Map<String, Integer>> graph = new HashMap<>();
graph.put("A", Map.of("B", 2, "C", 3));
graph.put("B", Map.of("A", 2, "D", 4, "E", 5));
graph.put("C", Map.of("A", 3, "F", 1));
graph.put("D", Map.of("B", 4, "G", 2));
graph.put("E", Map.of("B", 5));
graph.put("F", Map.of("C", 1, "G", 3));
graph.put("G", Map.of("D", 2, "F", 3));
System.out.println(dijkstra(graph, "A"));
}
static class Pair {
int distance;
String vertex;
public Pair(int distance, String vertex) {
this.distance = distance;
this.vertex = vertex;
}
}
}
Here is an example of Prim’s minimum spanning tree algorithm implemented in Java:
import java.util.*;
class Prim {
public static Set<int[]> prim(Map<String, Map<String, Integer>> graph) {
Set<int[]> minimumSpanningTree = new HashSet<>();
Set<String> visited = new HashSet<>();
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (String vertex : graph.keySet()) {
for (String neighbor : graph.get(vertex).keySet()) {
heap.offer(new int[]{graph.get(vertex).get(neighbor), vertex, neighbor});
}
}
String startVertex = graph.keySet().iterator().next();
visited.add(startVertex);
while (!heap.isEmpty()) {
int[] edge = heap.poll();
int weight = edge[0];
String v1 = edge[1];
String v2 = edge[2];
if (!visited.contains(v2)) {
visited.add(v2);
minimumSpanningTree.add(new int[]{v1, v2, weight});
}
if (!visited.contains(v1)) {
visited.add(v1);
minimumSpanningTree.add(new int[]{v2, v1, weight});
}
}
return minimumSpanningTree;
}
public static void main(String[] args) {
Map<String, Map<String, Integer>> graph = new HashMap<>();
graph.put("A", Map.of("B", 2, "C", 3));
graph.put("B", Map.of("A", 2, "D", 4, "E", 5));
graph.put("C", Map.of("A", 3, "F", 1));
graph.put("D", Map.of("B", 4, "G", 2));
graph.put("E", Map.of("B", 5));
graph.put("F", Map.of("C", 1, "G", 3));
graph.put("G", Map.of("D", 2, "F", 3));
System.out.println(prim(graph));
}
}
In terms of Rust, there’s no implementation provided here since it’s a complex implementation and it’s beyond the scope of this response but you can find library crates such as “petgraph” which provides various graph algorithms including Dijkstra’s shortest path and Prim’s minimum spanning tree. In conclusion, Dijkstra’s shortest path and Prim’s minimum spanning tree are two powerful and widely used graph algorithms that can be implemented in various programming languages such as Python, JavaScript, Java and Rust. They both have a time complexity of O(E log V), making them suitable for solving problems on large graphs.