How to solve problems that involve Dijkstra’s Algorithm:
Below are the few problems that will help to identify how or when can we apply Dijkstra’s Algorithm in competitive programming problem:
Problem 1: You are given an undirected weighted graph with N vertices and M edges. You can make the weight of any one edge zero. The task is to compute shortest path from vertex 1 to vertex N such that you can reduce weight of any edge to 0.
Let’s see how we can apply Dijkstra’s Algorithm to above problem:
Observation: The above problem is a shortest path problem but with modification that weight of any one edge can be made 0. Now suppose we are making the weight of edge vertex v and u to 0, then there we get two cases:
Case 1: 1->v->u->N: We need to know the minimum distance between from vertex 1 to vertex v and vertex N to vertex u.
Case 2: 1->u->v->N: We need to know the minimum distance between from vertex 1 to vertex u and vertex N to vertex v.
Applying Dijkstra’s Algorithm: To compute the results of above two cases optimally we use Dijkstra’s Algorithm from vertex 1 and vertex N, since we need to know the minimum distance from vertex 1 and N to every other vertex.
Final Answer: Our final answer will be the minimum of:
min(dis1[v]+dis2[u], dis1[u]+dis2[v]), for all edges(v-u), where dis1[a] represents the minimum distance from vertex 1 to vertex a and dis2[a] represents the minimum distance from vertex N to vertex a.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
// Dijkstra's algorithm function to compute minimum
// distances
vector<int> Dijkstra(int n, int m,
vector<vector<pair<int, int> > >& adj,
int src)
{
// Priority queue for min-heap
priority_queue<pair<int, int>, vector<pair<int, int> >,
greater<pair<int, int> > >
p;
// Initialize distances
vector<int> distance(n + 1, INT_MAX);
// Push the source vertex with a distance of 0
p.push(make_pair(0, src));
// Set the distance of the source vertex to 0
distance[src] = 0;
while (!p.empty()) {
int curr = p.top().second;
int l = p.top().first;
p.pop();
// Skip if this vertex has already been processed
// with a shorter distance
if (distance[curr] != l) {
continue;
}
// Explore neighbors and update distances
for (auto x : adj[curr]) {
// Neighbor vertex
int d = x.first;
// Edge weight
int len = x.second;
// Update the distance if a shorter path is
// found
if (distance[d] > len + distance[curr]) {
distance[d] = len + distance[curr];
// Push the updated distance and vertex
p.push(make_pair(distance[d], d));
}
}
}
return distance;
}
// Function to solve the problem
void solve(int n, int m, vector<vector<int> >& edges)
{
// Adjacency list for edges
vector<vector<pair<int, int> > > adj(n + 1);
// Build the adjacency list for edges
for (int i = 0; i < m; i++) {
int x = edges[i][0], y = edges[i][1],
z = edges[i][2];
adj[x].push_back({ y, z });
adj[y].push_back({ x, z });
}
// Compute minimum distances from vertex 1 and vertex N
vector<int> dis1 = Dijkstra(n, m, adj, 1);
vector<int> dis2 = Dijkstra(n, m, adj, n);
int ans = INT_MAX;
// Iterate through all edges to find the minimum cost of
// reducing an edge to 0
for (int i = 0; i < m; i++) {
int v = edges[i][0], u = edges[i][1];
// Calculate the cost of reducing edge (v, u) to 0
ans = min(
ans, min(dis1[v] + dis2[u], dis1[u] + dis2[v]));
}
// Output the minimum cost
cout << ans << "\n";
}
int main()
{
int n = 4, m = 4;
// Edges as (vertex1, vertex2, weight)
vector<vector<int> > edges = {
{ 1, 2, 3 }, { 2, 3, 1 }, { 1, 3, 7 }, { 3, 4, 2 }
};
// Call the solve function to find the answer
solve(n, m, edges);
return 0;
}
import java.util.*;
public class DijkstraAlgorithm {
// Dijkstra's algorithm function to compute minimum
// distances
public static List<Integer>
dijkstra(int n, int m, List<List<Pair> > adj, int src)
{
// Priority queue for min-heap
PriorityQueue<Pair> p = new PriorityQueue<>(
Comparator.comparingInt(pair -> pair.first));
// Initialize distances
List<Integer> distance = new ArrayList<>(
Collections.nCopies(n + 1, Integer.MAX_VALUE));
// Push the source vertex with a distance of 0
p.add(new Pair(0, src));
// Set the distance of the source vertex to 0
distance.set(src, 0);
while (!p.isEmpty()) {
int curr = p.peek().second;
int l = p.peek().first;
p.poll();
// Skip if this vertex has already been
// processed with a shorter distance
if (!distance.get(curr).equals(l)) {
continue;
}
// Explore neighbors and update distances
for (Pair x : adj.get(curr)) {
// Neighbor vertex
int d = x.first;
// Edge weight
int len = x.second;
// Update the distance if a shorter path is
// found
if (distance.get(d)
> len + distance.get(curr)) {
distance.set(d,
len + distance.get(curr));
// Push the updated distance and vertex
p.add(new Pair(distance.get(d), d));
}
}
}
return distance;
}
// Function to solve the problem
public static void solve(int n, int m,
List<List<Integer> > edges)
{
// Adjacency list for edges
List<List<Pair> > adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
// Build the adjacency list for edges
for (int i = 0; i < m; i++) {
int x = edges.get(i).get(0);
int y = edges.get(i).get(1);
int z = edges.get(i).get(2);
adj.get(x).add(new Pair(y, z));
adj.get(y).add(new Pair(x, z));
}
// Compute minimum distances from vertex 1 and
// vertex N
List<Integer> dis1 = dijkstra(n, m, adj, 1);
List<Integer> dis2 = dijkstra(n, m, adj, n);
int ans = Integer.MAX_VALUE;
// Iterate through all edges to find the minimum
// cost of reducing an edge to 0
for (int i = 0; i < m; i++) {
int v = edges.get(i).get(0);
int u = edges.get(i).get(1);
// Calculate the cost of reducing edge (v, u) to
// 0
ans = Math.min(
ans, Math.min(dis1.get(v) + dis2.get(u),
dis1.get(u) + dis2.get(v)));
}
// Output the minimum cost
System.out.println(ans);
}
public static void main(String[] args)
{
int n = 4, m = 4;
// Edges as (vertex1, vertex2, weight)
List<List<Integer> > edges = Arrays.asList(
Arrays.asList(1, 2, 3), Arrays.asList(2, 3, 1),
Arrays.asList(1, 3, 7), Arrays.asList(3, 4, 2));
// Call the solve function to find the answer
solve(n, m, edges);
}
}
// Pair class to store (vertex, weight) pairs
class Pair {
int first, second;
Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// This code is contributed by Aman.
import heapq
# Dijkstra's algorithm function to compute minimum distances
def Dijkstra(n, m, adj, src):
# Priority queue for min-heap
p = []
# Initialize distances
distance = [float('inf')] * (n + 1)
# Push the source vertex with a distance of 0
heapq.heappush(p, (0, src))
# Set the distance of the source vertex to 0
distance[src] = 0
while p:
l, curr = heapq.heappop(p)
# Skip if this vertex has already been processed with a shorter distance
if distance[curr] != l:
continue
# Explore neighbors and update distances
for d, len in adj[curr]:
# Update the distance if a shorter path is found
if distance[d] > len + distance[curr]:
distance[d] = len + distance[curr]
# Push the updated distance and vertex
heapq.heappush(p, (distance[d], d))
return distance
# Function to solve the problem
def solve(n, m, edges):
# Adjacency list for edges
adj = [[] for _ in range(n + 1)]
# Build the adjacency list for edges
for i in range(m):
x, y, z = edges[i]
adj[x].append((y, z))
adj[y].append((x, z))
# Compute minimum distances from vertex 1 and vertex N
dis1 = Dijkstra(n, m, adj, 1)
dis2 = Dijkstra(n, m, adj, n)
ans = float('inf')
# Iterate through all edges to find the minimum cost of reducing an edge to 0
for i in range(m):
v, u, _ = edges[i]
# Calculate the cost of reducing edge (v, u) to 0
ans = min(ans, min(dis1[v] + dis2[u], dis1[u] + dis2[v]))
# Output the minimum cost
print(ans)
n = 4
m = 4
# Edges as (vertex1, vertex2, weight)
edges = [
[1, 2, 3], [2, 3, 1], [1, 3, 7], [3, 4, 2]
]
solve(n, m, edges)
using System;
using System.Collections.Generic;
public class WeightedEdge {
public int Vertex
{
get;
set;
}
public int Weight
{
get;
set;
}
}
public class Solution {
// Dijkstra's algorithm function to compute minimum
// distances
public static List<int>
Dijkstra(int n, int m, List<List<WeightedEdge> > adj,
int src)
{
// Priority queue for min-heap
var p = new SortedSet<Tuple<int, int> >(
Comparer<Tuple<int, int> >.Create(
(a, b) = > a.Item1 == b.Item1
? a.Item2.CompareTo(b.Item2)
: a.Item1.CompareTo(b.Item1)));
// Initialize distances
var distance = new List<int>(new int[n + 1]);
for (int i = 0; i < n + 1; i++) {
distance[i] = int.MaxValue;
}
// Push the source vertex with a distance of 0
p.Add(new Tuple<int, int>(0, src));
distance[src] = 0;
while (p.Count > 0) {
var curr = p.Min;
p.Remove(curr);
int l = curr.Item1;
int current = curr.Item2;
// Skip if this vertex has already been
// processed with a shorter distance
if (distance[current] != l) {
continue;
}
// Explore neighbors and update distances
foreach(var x in adj[current])
{
int d = x.Vertex;
int len = x.Weight;
// Update the distance if a shorter path is
// found
if (distance[d] > len + distance[current]) {
distance[d] = len + distance[current];
p.Add(new Tuple<int, int>(distance[d],
d));
}
}
}
return distance;
}
// Function to solve the problem
public static void Solve(int n, int m,
List<List<int> > edges)
{
// Adjacency list for edges
var adj = new List<List<WeightedEdge> >(
new List<WeightedEdge>[ n + 1 ]);
for (int i = 0; i < n + 1; i++) {
adj[i] = new List<WeightedEdge>();
}
// Build the adjacency list for edges
for (int i = 0; i < m; i++) {
int x = edges[i][0], y = edges[i][1],
z = edges[i][2];
adj[x].Add(
new WeightedEdge{ Vertex = y, Weight = z });
adj[y].Add(
new WeightedEdge{ Vertex = x, Weight = z });
}
// Compute minimum distances from vertex 1 and
// vertex N
var dis1 = Dijkstra(n, m, adj, 1);
var dis2 = Dijkstra(n, m, adj, n);
int ans = int.MaxValue;
// Iterate through all edges to find the minimum
// cost of reducing an edge to 0
for (int i = 0; i < m; i++) {
int v = edges[i][0], u = edges[i][1];
// Calculate the cost of reducing edge (v, u) to
// 0
ans = Math.Min(ans,
dis1[v] + edges[i][2] + dis2[u]);
ans = Math.Min(ans,
dis1[u] + edges[i][2] + dis2[v]);
}
// Output the minimum cost
Console.WriteLine(ans);
}
public static void Main()
{
int n = 4, m = 4;
// Edges as (vertex1, vertex2, weight)
List<List<int> > edges = new List<List<int> >{
new List<int>{ 1, 2, 3 },
new List<int>{ 2, 3, 1 },
new List<int>{ 1, 3, 7 },
new List<int>{ 3, 4, 2 }
};
// Call the Solve function to find the answer
Solve(n, m, edges);
}
}
class MinHeap {
constructor() {
this.heap = [];
}
push(val) {
this.heap.push(val);
this.heapifyUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return null;
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this.heapifyDown(0);
}
return top;
}
heapifyUp(idx) {
while (idx > 0) {
const parentIdx = Math.floor((idx - 1) / 2);
if (this.heap[parentIdx][0] > this.heap[idx][0]) {
[this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
idx = parentIdx;
} else {
break;
}
}
}
heapifyDown(idx) {
while (idx < this.heap.length) {
let leftChild = 2 * idx + 1;
let rightChild = 2 * idx + 2;
let smallest = idx;
if(leftChild < this.heap.length && this.heap[leftChild][0] < this.heap[smallest][0]){
smallest = leftChild;
}
if(rightChild < this.heap.length && this.heap[rightChild][0] < this.heap[smallest][0]){
smallest = rightChild;
}
if (smallest !== idx) {
[this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
idx = smallest;
} else {
break;
}
}
}
}
function dijkstra(n, m, adj, src) {
// Priority queue for min-heap
const pq = new MinHeap();
pq.push([0, src]);
// Initialize distances
const distance = Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
distance[src] = 0;
while (pq.heap.length > 0) {
const [currDist, curr] = pq.pop();
// Skip if this vertex has already been processed
// with a shorter distance
if (currDist > distance[curr]) {
continue;
}
// Explore neighbors and update distances
for (const [neighbor, weight] of adj[curr]) {
const newDist = currDist + weight;
if (newDist < distance[neighbor]) {
distance[neighbor] = newDist;
pq.push([newDist, neighbor]);
}
}
}
return distance;
}
function solve(n, m, edges) {
// Adjacency list for edges
const adj = Array.from({ length: n + 1 }, () => []);
// Build the adjacency list for edges
for (const [x, y, z] of edges) {
adj[x].push([y, z]);
adj[y].push([x, z]);
}
// Compute minimum distances from vertex 1 and vertex N
const dis1 = dijkstra(n, m, adj, 1);
const dis2 = dijkstra(n, m, adj, n);
let ans = Number.MAX_SAFE_INTEGER;
// Iterate through all edges to find the minimum cost of
// reducing an edge to 0
for (const [v, u, weight] of edges) {
// Calculate the cost of reducing edge (v, u) to 0
ans = Math.min(ans, dis1[v] + dis2[u], dis1[u] + dis2[v]);
}
// Output the minimum cost
console.log(ans);
}
const n = 4;
const m = 4;
// Edges as (vertex1, vertex2, weight)
const edges = [
[1, 2, 3],
[2, 3, 1],
[1, 3, 7],
[3, 4, 2]
];
// Call the solve function to find the answer
solve(n, m, edges);
Output
2
Time Complexity: O(mlogn), m is number of edges and n is number of edges.
Auxiliary space: O(n+m),
Problem 2: You are given an undirected weighted graph with N vertices. There are m1 edges which are of TYPE1 and m2 edges which are of TYPE2. The ith TYPE1 edge goes from vertex vi to vertex ui , and weight wi. The ith TYPE2 edge goes from vertex 1 to vertex vi , and weight wi. The task is to determine the maximum TYPE2 edges which can be removed such that the shortest path from vertex 1 to every other vertex remains the same. There can be multiple edges of same type between two vertices.
Let’s see how we can apply Dijkstra’s Algorithm to above problem:
Observation: The ith edge of TYPE 2 which goes from vertex 1 to vertex vi and has weight wi, can be removed if a there exist a path without using this edge such that total distance of this path is less than or equal to wi. We will first use all edges of TYPE 2, and update the dis[] array, dis[i] represents the shortest distance from vertex 1 to vertex ai and create vis[]
Applying Dijkstra’s Algorithm: Choose a vertex v with the smallest value of dis[v] that is unmarked. Set vis[v] as true (mark it). Then iterate over all edges (v->u) , and if dis[v] + w <= dis[u], then we don’t need any edges of TYPE 2 that goes from vertex 1 to vertex u since there exist a path without using the edges (1->u) such that total distance of this path is less than or equal to weight of any edge of TYPE 2 hat goes from vertex 1 to vertex u. We can set ans[u]=false, which indicates that we don’t need any edges of TYPE 2 that goes from vertex 1 to vertex u.
Final answer: If ans[i]=true, then we need a edge of type 2 that goes from vertex 1 to vertex 1. Thus, we can determine at the end the number of vertices i for which ans[i]=true and store it in count.
Hence our final answer will be m2-count, where m2 is the number of edges of TYPE 2 and count is the number of edges of TYPE 2 which are required.
Below is the implementation of above approach:
#include <bits/stdc++.h>
using namespace std;
// Function to solve the problem
void solve(int n, int m1, int m2,
vector<vector<int> >& edges1,
vector<vector<int> >& edges2)
{
// Adjacency list for TYPE 1 edges
vector<vector<pair<int, int> > > adj(n + 1);
// Array to mark which TYPE 2 edges are needed
vector<bool> ans(n + 1);
// Array to store the shortest distances
vector<int> dis(n + 1, INT_MAX);
// Build the adjacency list for TYPE 1 edges
for (int i = 0; i < m1; i++) {
int x = edges1[i][0], y = edges1[i][1],
z = edges1[i][2];
adj[x].push_back({ y, z });
adj[y].push_back({ x, z });
}
// Initialize dis[] and ans[] arrays for TYPE 2 edges
for (int i = 0; i < m2; i++) {
int x = edges2[i][0], y = edges2[i][1];
dis[x] = min(dis[x], y);
ans[x] = true;
}
set<pair<int, int> > pq;
dis[1] = 0;
pq.insert({ 0, 1 });
// Initialize the set with the distances
for (int i = 2; i <= n; i++) {
if (dis[i] != INT_MAX) {
pq.insert({ dis[i], i });
}
}
// Dijkstra's algorithm
while (!pq.empty()) {
int curr = (*pq.begin()).second;
int l = (*pq.begin()).first;
pq.erase(pq.begin());
for (auto x : adj[curr]) {
int d = x.first;
int len = x.second;
// Update the distance and ans[] if a shorter
// path is found
if (dis[d] >= len + dis[curr]) {
if (pq.find({ dis[d], d }) != pq.end()) {
pq.erase({ dis[d], d });
}
dis[d] = len + dis[curr];
pq.insert({ dis[d], d });
ans[d] = false;
}
}
}
int count = 0;
for (int i = 1; i <= n; i++) {
if (ans[i] == true) {
count++;
}
}
// Output the maximum number of TYPE 2 edges that can be
// removed
cout << m2 - count << "\n";
}
int main()
{
int n = 5, m1 = 5, m2 = 3;
// TYPE1 edges
vector<vector<int> > edges1 = { { 1, 2, 1 },
{ 2, 3, 2 },
{ 1, 3, 3 },
{ 3, 4, 4 },
{ 1, 5, 5 } };
// TYPE2 edges
vector<vector<int> > edges2
= { { 3, 5 }, { 4, 5 }, { 5, 5 } };
// Call the solve function to find the answer
solve(n, m1, m2, edges1, edges2);
}
import java.util.*;
public class MaximumRemovableEdges {
// Function to solve the problem
static void solve(int n, int m1, int m2,
ArrayList<ArrayList<Integer> > edges1,
ArrayList<ArrayList<Integer> > edges2)
{
// Adjacency list for TYPE 1 edges
ArrayList<ArrayList<Pair> > adj
= new ArrayList<>(n + 1);
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
// Array to mark which TYPE 2 edges are needed
boolean[] ans = new boolean[n + 1];
// Array to store the shortest distances
int[] dis = new int[n + 1];
Arrays.fill(dis, Integer.MAX_VALUE);
// Build the adjacency list for TYPE 1 edges
for (ArrayList<Integer> edge : edges1) {
int x = edge.get(0), y = edge.get(1),
z = edge.get(2);
adj.get(x).add(new Pair(y, z));
adj.get(y).add(new Pair(x, z));
}
// Initialize dis[] and ans[] arrays for TYPE 2
// edges
for (ArrayList<Integer> edge : edges2) {
int x = edge.get(0), y = edge.get(1);
dis[x] = Math.min(dis[x], y);
ans[x] = true;
}
TreeSet<Pair> pq = new TreeSet<>(
Comparator.comparingInt(o -> o.weight));
dis[1] = 0;
pq.add(new Pair(0, 1));
// Initialize the set with the distances
for (int i = 2; i <= n; i++) {
if (dis[i] != Integer.MAX_VALUE) {
pq.add(new Pair(dis[i], i));
}
}
// Dijkstra's algorithm
while (!pq.isEmpty()) {
Pair curr = pq.pollFirst();
int currVertex = curr.vertex;
int currDist = curr.weight;
for (Pair x : adj.get(currVertex)) {
int d = x.vertex;
int len = x.weight;
// Update the distance and ans[] if a
// shorter path is found
if (dis[d] >= len + dis[currVertex]) {
pq.remove(new Pair(dis[d], d));
dis[d] = len + dis[currVertex];
pq.add(new Pair(dis[d], d));
ans[d] = false;
}
}
}
int count = 0;
for (int i = 1; i <= n; i++) {
if (ans[i]) {
count++;
}
}
// Output the maximum number of TYPE 2 edges that
// can be removed
System.out.println(m2 - count);
}
public static void main(String[] args)
{
int n = 5, m1 = 5, m2 = 3;
// TYPE1 edges
ArrayList<ArrayList<Integer> > edges1
= new ArrayList<>(Arrays.asList(
new ArrayList<>(Arrays.asList(1, 2, 1)),
new ArrayList<>(Arrays.asList(2, 3, 2)),
new ArrayList<>(Arrays.asList(1, 3, 3)),
new ArrayList<>(Arrays.asList(3, 4, 4)),
new ArrayList<>(Arrays.asList(1, 5, 5))));
// TYPE2 edges
ArrayList<ArrayList<Integer> > edges2
= new ArrayList<>(Arrays.asList(
new ArrayList<>(Arrays.asList(3, 5)),
new ArrayList<>(Arrays.asList(4, 5)),
new ArrayList<>(Arrays.asList(5, 5))));
// Call the solve function to find the answer
solve(n, m1, m2, edges1, edges2);
}
static class Pair {
int weight;
int vertex;
Pair(int weight, int vertex)
{
this.weight = weight;
this.vertex = vertex;
}
}
}
from heapq import heappush, heappop
# Function to solve the problem
def solve(n, m1, m2, edges1, edges2):
# Adjacency list for TYPE 1 edges
adj = [[] for _ in range(n + 1)]
# Array to mark which TYPE 2 edges are needed
ans = [False] * (n + 1)
# Array to store the shortest distances
dis = [float('inf')] * (n + 1)
# Build the adjacency list for TYPE 1 edges
for edge in edges1:
x, y, z = edge
adj[x].append((y, z))
adj[y].append((x, z))
# Initialize dis[] and ans[] arrays for TYPE 2 edges
for edge in edges2:
x, y = edge
dis[x] = min(dis[x], y)
ans[x] = True
pq = []
dis[1] = 0
heappush(pq, (0, 1))
# Dijkstra's algorithm
while pq:
l, curr = heappop(pq)
for x in adj[curr]:
d, length = x
# Update the distance and ans[] if a shorter path is found
if dis[d] >= length + dis[curr]:
dis[d] = length + dis[curr]
heappush(pq, (dis[d], d))
ans[d] = False
count = sum(1 for i in range(1, n + 1) if ans[i])
# Output the maximum number of TYPE 2 edges that can be removed
print(m2 - count)
# Main function
def main():
n = 5
m1 = 5
m2 = 3
# TYPE1 edges
edges1 = [[1, 2, 1],
[2, 3, 2],
[1, 3, 3],
[3, 4, 4],
[1, 5, 5]]
# TYPE2 edges
edges2 = [[3, 5], [4, 5], [5, 5]]
# Call the solve function to find the answer
solve(n, m1, m2, edges1, edges2)
if __name__ == "__main__":
main()
# this code is ocntributed by Prachi
// Function to solve the problem
function solve(n, m1, m2, edges1, edges2) {
// Adjacency list for TYPE 1 edges
let adj = Array.from({ length: n + 1 }, () => []);
// Array to mark which TYPE 2 edges are needed
let ans = Array(n + 1).fill(false);
// Array to store the shortest distances
let dis = Array(n + 1).fill(Number.MAX_SAFE_INTEGER);
// Build the adjacency list for TYPE 1 edges
for (let i = 0; i < m1; i++) {
let [x, y, z] = edges1[i];
adj[x].push([y, z]);
adj[y].push([x, z]);
}
// Initialize dis[] and ans[] arrays for TYPE 2 edges
for (let i = 0; i < m2; i++) {
let [x, y] = edges2[i];
dis[x] = Math.min(dis[x], y);
ans[x] = true;
}
let pq = new Set();
dis[1] = 0;
pq.add([0, 1]);
// Initialize the set with the distances
for (let i = 2; i <= n; i++) {
if (dis[i] !== Number.MAX_SAFE_INTEGER) {
pq.add([dis[i], i]);
}
}
// Dijkstra's algorithm
while (pq.size > 0) {
let curr = Array.from(pq)[0][1];
let l = Array.from(pq)[0][0];
pq.delete(Array.from(pq)[0]);
for (let [d, len] of adj[curr]) {
// Update the distance and ans[] if a shorter path is found
if (dis[d] >= len + dis[curr]) {
for (let entry of pq) {
if (entry[1] === d) {
pq.delete(entry);
break;
}
}
dis[d] = len + dis[curr];
pq.add([dis[d], d]);
ans[d] = false;
}
}
}
let count = 0;
for (let i = 1; i <= n; i++) {
if (ans[i] === true) {
count++;
}
}
// Output the maximum number of TYPE 2 edges that can be removed
console.log(m2 - count);
}
// Main function
function main() {
let n = 5, m1 = 5, m2 = 3;
// TYPE1 edges
let edges1 = [[1, 2, 1],
[2, 3, 2],
[1, 3, 3],
[3, 4, 4],
[1, 5, 5]];
// TYPE2 edges
let edges2 = [[3, 5], [4, 5], [5, 5]];
// Call the solve function to find the answer
solve(n, m1, m2, edges1, edges2);
}
// Call the main function
main();
//This code is contributed by Kishan.
Output
2
Time Complexity: O(mlogn), m is number of edges of TYPE1.
Auxiliary space: O(n+m),
Dijkstra’s Algorithm for Competitive Programming
Dijkstra’s algorithm, devised by computer scientist Edsger Dijkstra, is a fundamental graph search algorithm used to find the shortest path between nodes in a weighted graph. In this article, we will learn about how Dijkstra’s algorithm can be used for solving problems in Competitive Programming.
Table of Content
- What is Dijkstra’s Algorithm?
- Implementation of Dijkstra’s Algorithm
- How to solve problems that involve Dijkstra’s Algorithm
- Practice Problems on Dijkstra’s Algorithm for Competitive Programming