Distance between the vertices (Editorial)

The number of vertices in the graph is large, so we use a priority queue to implement Dijkstra's algorithm.

Example

The graph given in the example, has the following form:

Algorithm implementation

Declare a constant for infinity.

#define INF 0x3F3F3F3F

Declare a structure $g$ for storing the weighted graph. Each element $g [i]$ is a list of pairs (vertex, distance).

vector<vector<pair<int, int> > > g;

The function Dijkstra implements Dijkstra's algorithm starting from the vertex $s t a r t$ .

void Dijkstra(vector<vector<pair<int, int>>>& g, vector<int>& d, 
              int start)
{

Declare and initialize the priority queue $pq$ . The elements of this queue will be pairs (distance from the source to the vertex, vertex). Thus, the vertex at the top of the queue will always be the one with the smallest distance from the source.

priority_queue<pair<int, int>, vector<pair<int, int>>, 
               greater<pair<int, int>>> pq;
pq.push({0, start});

Initialize the array of shortest distances $d$ . The vertices of the graph are numbered from $1$ to $n$ .

  d = vector<int>(n + 1, INF);
  d[start] = 0;

Continue the Dijkstra's algorithm until the queue is empty.

  while (!pq.empty())
  {

Extract the pair $e$ from the top of the priority queue.

    pair<int, int> e = pq.top(); pq.pop();
    int v = e.second; // node

Check if the vertex $v$ is a dummy vertex. If the distance to $v$ is greater than the already computed value $d [v]$ , ignore this vertex.

    if (e.first > d[v]) continue; // distance > d[v]

Iterate over all vertices $t o$ adjacent to $v$ . The distance from $v$ to $t o$ is $cos t$ .

    for (auto edge: g[v])
    {
      int to = edge.first;
      int cost = edge.second;

If the edge $(v, t o)$ (v, to) relaxes, update the value of $d [t o]$ and insert the pair $(d [t o], t o)$ (d[to], to) into the queue.

      if (d[v] + cost < d[to])
      {
        d[to] = d[v] + cost;
        pq.push({d[to], to});
      }
    }
  }
}

C++

The main part of the program. Read the input data.

scanf("%d %d %d %d", &n, &m, &start, &fin);
g.resize(n + 1);
for (i = 0; i < m; i++)
{

Read the undirected edge $(b, e)$ with weight $w$ and add it to the graph $g$ .

  scanf("%d %d %d", &b, &e, &w);
  g[b].push_back({e, w});
  g[e].push_back({b, w});
}

Run Dijkstra's algorithm from the starting vertex $s t a r t$ .

Dijkstra(g, dist, start);

Print the shortest path distance $d i s t [f in]$ dist[fin]. If $d i s t [f in]$ dist[fin] is equal to infinity, then the path does not exist.

if (dist[fin] == INF)
  printf("-1\n");
else
  printf("%d\n", dist[fin]);

Algorithm implementation — edge structure

Declare a constant for infinity.

#define INF 0x3F3F3F3F

Declare an array of shortest distances $d i s t$ .

vector<int> dist;

The $e d g e$ structure stores information about an edge: the vertex $n o d e$ it leads to and its weight $d i s t$ .

struct edge
{
  int node, dist;
  edge(int node, int dist) : node(node), dist(dist) {}
};

The $e d g e$ structure will also be used in the priority queue. The queue stores the vertices of the graph, where:

$n o d e$ is the vertex number;
$d i s t$ is the current distance from the start vertex to vertex $n o d e$ .

The vertex at the top of the queue will be the one with the smallest $d i s t$ value.

bool operator< (edge a, edge b)
{
  return a.dist > b.dist;
}

Declare the adjacency list $g$ of the graph.

vector<vector<edge> > g;

The function Dijkstra implements Dijkstra's algorithm starting from the vertex $s t a r t$ .

void Dijkstra(vector<vector<edge> > &g, vector<int> &d, int start)
{

  priority_queue<edge> pq;
  pq.push(edge(start, 0));

Initialize the array of shortest distances $d$ . The vertices of the graph are numbered from $1$ to $n$ .

  d = vector<int>(n + 1, INF);
  d[start] = 0;

Continue the Dijkstra's algorithm until the queue is empty.

  while (!pq.empty())
  {

Extract the pair $e$ from the top of the priority queue.

    edge e = pq.top(); pq.pop();
    int v = e.node;

Check if the vertex $v$ is a dummy vertex. If the distance to $v$ is greater than the already computed value $d [v]$ , ignore this vertex.

    if (e.dist > d[v]) continue;

Iterate over all vertices $t o$ adjacent to $v$ . The distance from $v$ to $t o$ is $cos t$ .

    for (auto ed : g[v])
    {
      int to = ed.node;
      int cost = ed.dist;

If the edge $(v, t o)$ (v, to) relaxes, update the value of $d [t o]$ and insert the pair $(d [t o], t o)$ (d[to], to) into the queue.

      if (d[v] + cost < d[to])
      {
        d[to] = d[v] + cost;
        pq.push(edge(to, d[to]));
      }
    }
  }
}

C++

The main part of the program. Read the input data.

scanf("%d %d %d %d", &n, &m, &start, &fin);
g.resize(n + 1);
for (i = 0; i < m; i++)
{

Read the undirected edge $(b, e)$ with weight $w$ and add it to the graph $g$ .

  scanf("%d %d %d", &b, &e, &w);
  g[b].push_back(edge(e, w));
  g[e].push_back(edge(b, w));
}

Run Dijkstra's algorithm from the starting vertex $s t a r t$ .

Dijkstra(g, dist, start);

Print the shortest path distance $d i s t [f in]$ dist[fin]. If $d i s t [f in]$ dist[fin] is equal to infinity, then the path does not exist.

if (dist[fin] == INF)
  printf("-1\n");
else
  printf("%d\n", dist[fin]);

Java implementation

import java.util.*;

class Node implements Comparator<Node> 
{
  public int node, dist;
  
  Node() {}
  
  Node(int node, int dist)
  {
    this.node = node;
    this.dist = dist;
  }
  
  @Override
  public int compare(Node a, Node b) 
  { 
    return a.dist - b.dist; 
  }   
};

public class Main 
{
  // Adjacency list representation of the edges 
  static List<List<Node> > g;
  static int dist[];
  static int INF = Integer.MAX_VALUE;
  static int n, m; 
  
  static void dijkstra(int start)
  {
    PriorityQueue<Node> pq = new PriorityQueue<Node>(n+1, new Node());	  
    for (int i = 0; i <= n; i++) 
      dist[i] = Integer.MAX_VALUE;

    // Add source node to the priority queue 
    pq.add(new Node(start, 0)); 

    // Distance to the source is 0 
    dist[start] = 0;

    while(!pq.isEmpty())
    {
      Node e = pq.poll();
      int v = e.node;
      if (e.dist > dist[v]) continue;

      for(int j = 0; j < g.get(v).size(); j++)
      {
        int to = g.get(v).get(j).node;
        int cost = g.get(v).get(j).dist;
        if (dist[v] + cost < dist[to])
        {
          dist[to] = dist[v] + cost;
          pq.add(new Node(to,dist[to]));
        }
      }
    }
  }
  
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    n = con.nextInt();
    m = con.nextInt();
    int start = con.nextInt();
    int fin = con.nextInt();

    g = new ArrayList<List<Node> >();
    // Initialize list for every node 
    for (int i = 0; i <= n; i++) 
    { 
      List<Node> item = new ArrayList<Node>(); 
      g.add(item); 
    }    
    
    for(int i = 0; i < m; i++)
    {
      int b = con.nextInt();
      int e = con.nextInt();
      int w = con.nextInt();

      g.get(b).add(new Node(e,w));
      g.get(e).add(new Node(b,w));
    }
    
    dist = new int[n+1];
    dijkstra(start); 
    
    if (dist[fin] == INF)
      System.out.println(-1);
    else
      System.out.println(dist[fin]);
    con.close();
  }
}

Java

Python implementation

Import the priority queue.

from queue import PriorityQueue

Declare a constant for infinity $I N F$ .

INF = 10**9

The function Dijkstra implements Dijkstra's algorithm starting from the vertex $s t a r t$ .

def dijkstra(graph, dist, start):

  pq = PriorityQueue()
  pq.put((0, start))

Initialize the array of shortest distances $d i s t$ . The vertices of the graph are numbered from $1$ to $n$ .

  dist.extend([INF] * (n + 1))
  dist[start] = 0

Continue the Dijkstra's algorithm until the queue is empty.

  while not pq.empty():

Extract the pair $(c u r_{d} i s t, v)$ (cur_dist, v) from the top of the priority queue.

    cur_dist, v = pq.get()

Check if the vertex $v$ is a dummy vertex. If the distance to $v$ is greater than the already computed value $d [v]$ , ignore this vertex.

    if cur_dist > dist[v]: continue

Iterate over all vertices $t o$ adjacent to $v$ . The distance from $v$ to $t o$ is $cos t$ .

    for to, cost in graph[v]:

If the edge $(v, t o)$ (v, to) relaxes, update the value of $d [t o]$ and insert the pair $(d [t o], t o)$ (d[to], to) into the queue.

      if dist[v] + cost < dist[to]:
        dist[to] = dist[v] + cost
        pq.put((dist[to], to))

The main part of the program. Read the input data.

n, m = map(int, input().split())
start, fin = map(int, input().split())
g = [[] for _ in range(n + 1)]

for _ in range(m):

Read the undirected edge $(b, e)$ with weight $w$ and add it to the graph $g$ .

  b, e, w = map(int, input().split())
  g[b].append((e, w))
  g[e].append((b, w))

Initialize the list of shortest distances $d i s t$ .

dist = []

Run Dijkstra's algorithm from the starting vertex $s t a r t$ .

dijkstra(g, dist, start)

Print the shortest path distance $d i s t [f in]$ dist[fin]. If $d i s t [f in]$ dist[fin] is equal to infinity, then the path does not exist.

if dist[fin] == INF:
  print("-1")
else:
  print(dist[fin])