Відстань між вершинами (Розбір)

Кількість вершин у графі велика, тому для реалізації алгоритму Дейкстри використовуємо чергу з пріоритетом.

Приклад

Граф, наведений у прикладі, має вигляд:

Реалізація алгоритму

Оголосимо константу нескінченність.

#define INF 0x3F3F3F3F

Оголосимо структуру $g$ для зберігання зваженого графа. Кожен елемент $g [i]$ є списком пар (вершина, відстань).

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

Функція Dijkstra реалізує алгоритм Дейкстри, починаючи з вершини $s t a r t$ .

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

Оголосимо та ініціалізуємо чергу з пріоритетами $pq$ . Елементами цієї черги будуть пари (відстань до вершини від витоку, вершина). Таким чином, на вершині черги завжди знаходиться вершина графа з найменшою відстанню від витоку.

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

Ініціалізуємо масив найкоротших відстаней $d$ . Вершини графа нумеруються з $1$ до $n$ .

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

Продовжуємо алгоритм Дейкстри, поки черга не порожня.

  while (!pq.empty())
  {

Витягуємо пару $e$ з вершини черги з пріоритетами.

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

Перевіряємо, чи є вершина $v$ фіктивною. Якщо відстань до $v$ більша, ніж уже обчислене значення $d [v]$ , то ігноруємо цю вершину.

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

Перебираємо всі вершини $t o$ , суміжні з $v$ . Відстань від $v$ до $t o$ дорівнює $cos t$ .

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

Якщо ребро $(v, t o)$ (v, to) релаксується, то перераховуємо значення $d [t o]$ і заносимо пару $(d [t o], t o)$ (d[to], to) в чергу.

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

C++

Основна частина програми. Читаємо вхідні дані.

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

Читаємо неорієнтоване ребро $(b, e)$ вагою $w$ і додаємо його до графа $g$ .

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

Запускаємо алгоритм Дейкстри з початкової вершини $s t a r t$ .

Dijkstra(g, dist, start);

Виводимо шуканий найкоротший шлях $d i s t [f in]$ dist[fin]. Якщо $d i s t [f in]$ dist[fin] дорівнює нескінченності, то шуканого шляху не існує.

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

Реалізація алгоритму — структура edge

Оголосимо константу нескінченність.

#define INF 0x3F3F3F3F

Оголосимо масив найкоротших відстаней $d i s t$ .

vector<int> dist;

Структура $e d g e$ зберігає інформацію про ребро: вершину $n o d e$ , в яку воно йде, та її вагу $d i s t$ .

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

Структура $e d g e$ також буде використана в черзі з пріоритетами. Черга зберігає вершини графа, де

$n o d e$ — номер вершини;
$d i s t$ — поточна відстань від початкової вершини до вершини $n o d e$ .

На вершині черги буде знаходиться вершина графа з найменшим значенням $d i s t$ .

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

Оголосимо список суміжності $g$ графа.

vector<vector<edge> > g;

Функція Dijkstra реалізує алгоритм Дейкстри, починаючи з вершини $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));

Ініціалізуємо масив найкоротших відстаней $d$ . Вершини графа нумеруються з $1$ до $n$ .

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

Продовжуємо алгоритм Дейкстри, поки черга не порожня.

  while (!pq.empty())
  {

Витягуємо пару $e$ з вершини черги з пріоритетами.

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

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

Перебираємо всі вершини $t o$ , суміжні з $v$ . Відстань від $v$ до $t o$ дорівнює $cos t$ .

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

Якщо ребро $(v, t o)$ (v, to) релаксується, то перераховуємо значення $d [t o]$ і заносимо пару $(d [t o], t o)$ (d[to], to) в чергу.

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

C++

Основна частина програми. Читаємо вхідні дані.

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

Читаємо неорієнтоване ребро $(b, e)$ вагою $w$ і додаємо його до графа $g$ .

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

Запускаємо алгоритм Дейкстри з початкової вершини $s t a r t$ .

Dijkstra(g, dist, start);

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

Java реалізація

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 реалізація

Імпортуємо чергу з пріоритетом.

from queue import PriorityQueue

Оголосимо константу $I N F$ .

INF = 10**9

Функція Dijkstra реалізує алгоритм Дейкстри, починаючи з вершини $s t a r t$ .

def dijkstra(graph, dist, start):

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

Ініціалізуємо список найкоротших відстаней $d i s t$ . Вершини графа нумеруються з $1$ до $n$ .

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

Продовжуємо алгоритм Дейкстри, поки черга не порожня.

  while not pq.empty():

Витягуємо пару $(c u r_{d} i s t, v)$ (cur_dist, v) з вершини черги з пріоритетами.

    cur_dist, v = pq.get()

Перевіряємо, чи є вершина $v$ фіктивною. Якщо відстань до $v$ більша, ніж уже обчислене значення $d i s t [v]$ dist[v], то ігноруємо цю вершину.

    if cur_dist > dist[v]: continue

Перебираємо всі вершини $t o$ , суміжні з $v$ . Відстань від $v$ до $t o$ дорівнює $cos t$ .

    for to, cost in graph[v]:

Якщо ребро $(v, t o)$ (v, to) релаксується, то перераховуємо значення $d [t o]$ і заносимо пару $(d i s t [t o], t o)$ (dist[to], to) в чергу.

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

Основна частина програми. Читаємо вхідні дані.

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

for _ in range(m):

Читаємо неорієнтоване ребро $(b, e)$ вагою $w$ і додаємо його до графа $g$ .

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

Ініціалізуємо список найкоротших відстаней $d i s t$ .

dist = []

Запускаємо алгоритм Дейкстри з початкової вершини $s t a r t$ .

dijkstra(g, dist, start)

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