Təpələr arasındakı məsafə (Həll təhlili)

Qrafda zirvələrin sayı çoxdur, buna görə Deykstra alqoritmasini implementasiya etmək üçün prioritet sıra istifadə edək.

Nümunə

Nümunədə verilən qraf aşağıdakı kimidir:

Alqoritmanın reallaşdırılması

Nəticəsiz dəyəri üçün sabit elan edək.

#define INF 0x3F3F3F3F

Çəkiyə malik qrafı saxlamaq üçün $g$ strukturu elan edək. Hər bir $g [i]$ elementi (zirvə, məsafə) cütləşmələri siyahısıdır.

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

Dijkstra funksiyası Deykstra alqoritmasını $s t a r t$ zirvəsindən başlayır.

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

Prioritet sıranı $pq$ elan edək və inicializasiya edək. Bu sıranın elementləri (mənbədən zirvəyə qədər məsafə, zirvə) cütü olacaqdır. Bu şəkildə, sıranın başında həmişə mənbədən ən qısa məsafədə olan zirvə olacaqdır.

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

Ən qısa məsafələrin $d$ massivini inicializasiya edək. Qrafın zirvələri $1$ -dən $n$ -ə qədər nömrələnir.

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

Deykstra alqoritmasını sıranı boş deyilənə qədər davam etdiririk.

  while (!pq.empty())
  {

Prioritet sıranın başından $e$ cütünü çıxardırıq.

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

Zirvənin $v$ saxta olub-olmadığını yoxlayırıq. Əgər $v$ -yə olan məsafə artıq hesablanmış $d [v]$ dəyərindən böyükdürsə, bu zirvəni nəzərə almırıq.

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

$t o$ ilə qonşu olan bütün zirvələri $v$ -dən keçiririk. $v$ -dən $t o$ -ya olan məsafə $cos t$ -a bərabərdir.

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

Əgər $(v, t o)$ (v, to) tərəfi rahatlaşırsa, $d [t o]$ dəyərini yenidən hesablayırıq və $(d [t o], t o)$ (d[to], to) cütünü sıraya əlavə edirik.

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

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$(b, e)$ qeyri- yönlü və $w$ çəkidə tərəf oxuyuruq və onu $g$ qrafına əlavə edirik.

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

Başlanğıc zirvədən $s t a r t$ Deykstra alqoritmasını işə salırıq.

Dijkstra(g, dist, start);

İstənilən ən qısa yolu $d i s t [f in]$ dist[fin] çap edirik. Əgər $d i s t [f in]$ dist[fin] nəticəsiz dəyərə bərabərsə, istənilən yol yoxdur deməkdir.

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

Alqoritmanın reallaşdırılması — edge strukturu

Nəticəsiz dəyəri üçün sabit elan edək.

#define INF 0x3F3F3F3F

Ən qısa məsafələr massivi $d i s t$ elan edək.

vector<int> dist;

$e d g e$ strukturu tərəf haqqında məlumatları saxlayır: $n o d e$ zirvəsi və onun $d i s t$ çəkisi.

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

$e d g e$ strukturu həmçinin prioritet sırada istifadə ediləcəkdir. Sıra qrafın zirvələrini saxlayır, burada

$n o d e$ — zirvənin nömrəsi;
$d i s t$ — başlanğıc zirvədən $n o d e$ zirvəsinə qədərki cari məsafədir.

Sıranın başında həmişə qrafın $d i s t$ dəyəri ən az olan zirvəsi olacaqdır.

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

Qrafın qonşuluq siyahısı $g$ elan edək.

vector<vector<edge> > g;

Dijkstra funksiyası Deykstra alqoritmasını $s t a r t$ zirvəsindən başlayır.

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

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

Ən qısa məsafələrin $d$ massivini inicializasiya edək. Qrafın zirvələri $1$ -dən $n$ -ə qədər nömrələnir.

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

Deykstra alqoritmasını sıranı boş deyilənə qədər davam etdiririk.

  while (!pq.empty())
  {

Prioritet sıranın başından $e$ cütünü çıxardırıq.

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

Zirvənin $v$ saxta olub-olmadığını yoxlayırıq. Əgər $v$ -yə olan məsafə artıq hesablanmış $d [v]$ dəyərindən böyükdürsə, bu zirvəni nəzərə almırıq.

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

$t o$ ilə qonşu olan bütün zirvələri $v$ -dən keçiririk. $v$ -dən $t o$ -ya olan məsafə $cos t$ -a bərabərdir.

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

Əgər $(v, t o)$ (v, to) tərəfi rahatlaşırsa, $d [t o]$ dəyərini yenidən hesablayırıq və $(d [t o], t o)$ (d[to], to) cütünü sıraya əlavə edirik.

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

C++

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

$(b, e)$ qeyri- yönlü və $w$ çəkidə tərəf oxuyuruq və onu $g$ qrafına əlavə edirik.

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

Başlanğıc zirvədən $s t a r t$ Deykstra alqoritmasını işə salırıq.

Dijkstra(g, dist, start);

İstənilən ən qısa yolu $d i s t [f in]$ dist[fin] çap edirik. Əgər $d i s t [f in]$ dist[fin] nəticəsiz dəyərə bərabərsə, istənilən yol yoxdur deməkdir.

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

Java implementasiyası

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 
{
  // Tərəflərin qonşuluq siyahı formasında təqdimatı 
  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;

    // Prioritet sıraya mənbə zirvəni əlavə edək 
    pq.add(new Node(start, 0)); 

    // Mənbəyə məsafə 0-a bərabərdir 
    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> >();
    // Hər bir zirvə üçün siyahı inizializasiya edək 
    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 implementasiyası

Prioritet sıranı import edirik.

from queue import PriorityQueue

$I N F$ sabitini elan edək.

INF = 10**9

Dijkstra funksiyası Deykstra alqoritmasını $s t a r t$ zirvəsindən başlayır.

def dijkstra(graph, dist, start):

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

Ən qısa məsafələrin $d i s t$ siyahısını inicializasiya edək. Qrafın zirvələri $1$ -dən $n$ -ə qədər nömrələnir.

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

Deykstra alqoritmasını sıranı boş deyilənə qədər davam etdiririk.

  while not pq.empty():

Prioritet sıranın başından $(c u r_{d} i s t, v)$ (cur_dist, v) cütünü çıxardırıq.

    cur_dist, v = pq.get()

Zirvənin $v$ saxta olub-olmadığını yoxlayırıq. Əgər $v$ -yə olan məsafə artıq hesablanmış $d i s t [v]$ dist[v] dəyərindən böyükdürsə, bu zirvəni nəzərə almırıq.

    if cur_dist > dist[v]: continue

$t o$ ilə qonşu olan bütün zirvələri $v$ -dən keçiririk. $v$ -dən $t o$ -ya olan məsafə $cos t$ -a bərabərdir.

    for to, cost in graph[v]:

Əgər $(v, t o)$ (v, to) tərəfi rahatlaşırsa, $d [t o]$ dəyərini yenidən hesablayırıq və $(d i s t [t o], t o)$ (dist[to], to) cütünü sıraya əlavə edirik.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

for _ in range(m):

$(b, e)$ qeyri- yönlü və $w$ çəkidə tərəf oxuyuruq və onu $g$ qrafına əlavə edirik.

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

Ən qısa məsafələrin $d i s t$ siyahısını inicializasiya edirik.

dist = []

Başlanğıc zirvədən $s t a r t$ Deykstra alqoritmasını işə salırıq.

dijkstra(g, dist, start)

İstənilən ən qısa yolu $d i s t [f in]$ dist[fin] çap edirik. Əgər $d i s t [f in]$ dist[fin] nəticəsiz dəyərə bərabərsə, istənilən yol yoxdur deməkdir.

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