Tworzenie macierzy sąsiedztwa i listy sąsiedztwa
Programy uruchomiono w środowisku Bloodshed Dev-C++ 4.9.9.2

       Programy

Poniższy program jest przykładową realizacją algorytmu Dijkstry. Definicja danych wejściowych jest następująca:

W pierwszym wierszu program odczytuje numer wierzchołka startowego v0. W następnym wierszu podajemy ilość krawędzi w grafie (skierowanym) m. W m kolejnych wierszach podajemy definicję krawędzi. Definicja składa się z trzech liczb x y w. Pierwsza i druga liczba określa wierzchołki grafu, które są ze sobą połączone tą krawędzią - krawędź biegnie od wierzchołka x do wierzchołka y. Trzecia liczba jest wagą krawędzi.

Na wyjściu program wypisuje znalezione najkrótsze ścieżki od wierzchołka v0 do wszystkich pozostałych wierzchołków. Oprócz ścieżki wypisywany jest również koszt przejścia tej ścieżki.

Do testów można wykorzystać przykładowe dane wejściowe:

obrazek 1
9
1 2 3
1 4 3
2 3 2
3 1 6
3 6 1
4 5 1
5 3 1
5 6 2
6 4 3

Wersja z wyszukiwaniem liniowym

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P012-01

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie
const int INF = 2147483647;

struct TNode
{
  int node;            // numer wierzchołka
  int weight;          // waga krawędzi
  struct TNode * next; // następny element listy
};

main()
{
  int i,j,u,n,m,x,y,z,v0;
  int d[MAX_N+1],p[MAX_N+1];
  bool QS[MAX_N+1];
  struct TNode *L[MAX_N+1],*pw;
  
// Inicjujemy struktury danych

  for(i = 1; i <= MAX_N; i++)
  {
    d[i]  = INF;    // koszty dojścia
    p[i]  = 0;      // poprzednik na ścieżce
    QS[i] = false; // przynależność do Q (false) lub S (true)
    L[i]  = NULL;   // lista sąsiedztwa
  }
  n = 0;

// Odczytujemy dane wejściowe

  cin >> v0; // odczytujemy numer wierzchołka startowego
  cin >> m;  // odczytujemy ilość krawędzi
  for(i = 1; i <= m; i++)
  {
    cin >> x >> y >> z; // odczytujemy krawędź
    if(x > n) n = x;
    if(y > n) n = y;
    pw = new TNode;
    pw->next = L[x]; pw->node = y; pw->weight = z; L[x] = pw;
  }
  cout << endl;

  d[v0] = 0; // koszt dojścia dla v0 jest zerowy
  
  for(i = 1; i <= n; i++)
  {

// szukamy wierzchołka w Q o najmniejszym d

    u = -1;
    for(j = 1; j <= n; j++)
      if(!QS[j] && ((u == -1) || (d[j] < d[u]))) u = j;

// znaleziony wierzchołek przenosimy do S

    QS[u] = true;

// Modyfikujemy odpowiednio wszystkich sąsiadów z Q

    pw = L[u];
    while(pw)
    {
      if(!QS[pw->node] && (d[pw->node] > d[u] + pw->weight))
      {
        d[pw->node] = d[u] + pw->weight;
        p[pw->node] = u;
      }
      pw = pw->next;
    }
  }

// Gotowe, wyświetlamy wyniki

  int stos[MAX_N],ws;
  
  for(i = 1; i <= n; i++)
  {
    cout << i << ": ";
    ws = 0; j = i;

// Wierzchołki z końca ścieżki umieszczamy na stosie

    while(j)
    {
      stos[ws++] = j; j = p[j];
    }

// Wypisujemy kolejne wierzchołki ze szczytu stosu

    while(ws) cout << stos[--ws] << " ";
    
// Wypisujemy koszt dojścia

    cout << "#" << d[i] << endl;    
  }        
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}
1
9
1 2 3
1 4 3
2 3 2
3 1 6
3 6 1
4 5 1
5 3 1
5 6 2
6 4 3

1: 1 #0
2: 1 2 #3
3: 1 2 3 #5
4: 1 4 #3
5: 1 4 5 #4
6: 1 4 5 6 #6

Wersja z kolejką priorytetową opartą na strukturze kopca

// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------
// Koło informatyczne 2006/7
//--------------------------
// P012-02

#include <iostream>

using namespace std;

const int MAX_N = 100; // maksymalna ilość wierzchołków w grafie
const int INF = 2147483647;

struct TNode
{
  int node;            // numer wierzchołka
  int weight;          // waga krawędzi
  struct TNode * next; // następny element listy
};

main()
{
  int i,j,u,n,m,x,y,z,v0;
  int d[MAX_N+1],p[MAX_N+1],heap[MAX_N+1],hp[MAX_N+1];
  bool QS[MAX_N+1];
  struct TNode *L[MAX_N+1],*pw;
  
// Inicjujemy struktury danych

  for(i = 1; i <= MAX_N; i++)
  {
    d[i]  = INF;         // koszty dojścia
    p[i]  = 0;           // poprzednik na ścieżce
    QS[i] = false;       // przynależność do Q (false) lub S (true)
    L[i]  = NULL;        // lista sąsiedztwa
    hp[i] = heap[i] = i; // kopiec
  }
  n = 0;

// Odczytujemy dane wejściowe

  cin >> v0; // odczytujemy numer wierzchołka startowego
  cin >> m;  // odczytujemy ilość krawędzi
  for(i = 1; i <= m; i++)
  {
    cin >> x >> y >> z; // odczytujemy krawędź
    if(x > n) n = x;
    if(y > n) n = y;
    pw = new TNode;
    pw->next = L[x]; pw->node = y; pw->weight = z; L[x] = pw;
  }
  cout << endl;

  int hlen  = n; // ilość wierzchołków w kopcu
  
  d[v0] = 0;     // koszt dojścia dla v0 jest zerowy

// Odtwarzamy własność kopca

  x = heap[1]; heap[1] = heap[v0]; heap[v0] = x;
  hp[v0] = 1; hp[1] = v0;
    
  for(i = 1; i <= n; i++)
  {

    u = heap[1];
    
// Usuwamy korzeń i odtwarzamy własność kopca

    int parent;
    
    heap[1] = heap[hlen]; hlen--;
    hp[heap[1]] = parent = 1;
    while(true)
    {
      int left = parent + parent;
      int right = left + 1;
      
      if(left > hlen) break;

      int dmin = d[heap[left]];
      int pmin = left;

      if((right <= hlen) && (dmin > d[heap[right]]))
      {
        dmin = d[heap[right]]; pmin = right;
      }
      if(d[heap[parent]] <= dmin) break;
      x = heap[parent]; heap[parent] = heap[pmin]; heap[pmin] = x;
      hp[heap[parent]] = parent; hp[heap[pmin]] = pmin;
      parent = pmin;
    }
    
// znaleziony wierzchołek przenosimy do S

    QS[u] = true;

// Modyfikujemy odpowiednio wszystkich sąsiadów z Q
    
    pw = L[u];
    while(pw)
    {
      if(!QS[pw->node] && (d[pw->node] > d[u] + pw->weight))
      {
        d[pw->node] = d[u] + pw->weight; p[pw->node] = u;

// Po zmianie d[v] odtwarzamy własność kopca

        int child = hp[pw->node];
        while(child > 1)
        {
          parent = child / 2;
          if(d[heap[parent]] <= d[heap[child]]) break;
          x = heap[parent]; heap[parent] = heap[child]; heap[child] = x;
          hp[heap[parent]] = parent; hp[heap[child]] = child;
          child = parent;
        }
      }
      pw = pw->next;
    }
  }

// Gotowe, wyświetlamy wyniki

  int stos[MAX_N],ws;
  
  for(i = 1; i <= n; i++)
  {
    cout << i << ": ";
    ws = 0; j = i;

// Wierzchołki z końca ścieżki umieszczamy na stosie

    while(j)
    {
      stos[ws++] = j; j = p[j];
    }

// Wypisujemy kolejne wierzchołki ze szczytu stosu

    while(ws) cout << stos[--ws] << " ";
    
// Wypisujemy koszt dojścia

    cout << "#" << d[i] << endl;    
  }        
  char s[1];
  cin.getline(s,1);
  cin.getline(s,1);
}


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2024 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe