algorytm.org

Implementacja w C/C++

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Dijkstry - Implementacja w C/C++
Ocena użytkownikóww: *****  / 6
SłabyŚwietny
Nadesłany przez Emil Hotkowski, 01 marca 2012 20:05
Kod przedstawiony poniżej przedstawia główną część rozwiązania problemu.
Pobierz pełne rozwiązanie.

Jeżeli nie odpowiada Ci sposób formatowania kodu przez autora skorzystaj z pretty printer'a i dostosuj go automatycznie do siebie.

dijkstra_kopce_c.cpp:
//*******************************
//*        Emil Hotkowski       *
//* Algorytm Dijkstry           *
//* Wersja kopcowa              * 
//* Kopiec własny               *
//* www.algorytm.org            *
//*******************************

#include <stdio.h>
#include <vector.h>
#define N 10000
#define NUM 2000000

using namespace std;
class kopiec{
      public:
      int tab[N];
      int node_nr[N];
      int size;
      kopiec();
      void insert_into(int v,int node);
      void delete_into();
      };
      
bool QS[N];//czy wierzcholek jest juz przerobiony czy nie 
//false oznacza ze juz jest albo jeszcze nie odwiedzono
//true ze ma jakas wartosc ale czeka w kopcu
vector <vector<int> > waga(N);//tablica vectorow (graf)
vector <vector<int> > graf(N);//-||-  (wagi)

int main()
{
    int n,m;//ilosc krawedzi !!!
    scanf("%d %d",&n,&m);//wczytuje ilosc wierzcholkow i krawedzi
    int * wartosc = new int [n+1] ;//tablica na wartosci
    
   for(int i = 0 ; i <= n ;i++)wartosc[i]=NUM;//wypelniam je duzym czyms
   
   
    for(int i = 1 ; i <= m;i++){
            int a,b,w;
            scanf("%d %d %d",&a,&b,&w);//wczytuje 
            graf[a].push_back(b);//wypelniam krawiedzi
            waga[a].push_back(w);//i wagi
       }
 
    wartosc[1]=0;   //wierzcholek nr 1
    QS[1]=false;    //juz odwiedzony
    kopiec K;       //nasz kopiec
    int ii = 1;     //aktualny wierzcholek na ktorym sie poruszamy
    for(int x = 1 ; x <= n ; x++){//wszystkie wierzchołki

            while(!graf[ii].empty()){//dopoki nie odwiedzimy wsyzstkich krawedzi wychodzacych z wierzchołka
    
            int z = graf[ii].back();//numer wierzchołka do ktorego mamy krawedz
            if(wartosc[z] > wartosc[ii]+waga[ii].back()){//sprawdzamy czy da sie poprawic droge , jezeli tak
                         wartosc[z] = wartosc[ii] + waga[ii].back(); //poprawiamy
                         QS[z]=true;//wierzchołek do kopca
                         K.insert_into(wartosc[z],z);//insert do kopca
                         
                          }//if waga
                          waga[ii].pop_back();//usuwamy wage
                          graf[ii].pop_back();//usuwamy wierzcholek
            }
            ii = K.node_nr[1];//sprawdzamy kolejny wierzcholek z najlżejszą drogą
            K.delete_into();//usuwamy go z kopca , ew czyscimy z nadmiaru wierzchołkow dublowanych
            }
   for(int i = 1 ; i <= n ; i++)printf("%d : %d\n",i,wartosc[i]);//wyswietlamy min drogi
   
    return 0;
}


kopiec::kopiec(){
                 size = 0;
                 }

void kopiec::insert_into(int v,int node){
       tab[size+1] = v;
       int s = size+1;
       node_nr[s] = node;
       while(s!=1)
       {
       if(tab[s/2] > tab[s]){
                   tab[s]=tab[s]^tab[s/2];
                   tab[s/2]=tab[s]^tab[s/2];
                   tab[s]=tab[s]^tab[s/2];
                   node_nr[s]=node_nr[s]^node_nr[s/2];
                   node_nr[s/2]=node_nr[s]^node_nr[s/2];
                   node_nr[s]=node_nr[s]^node_nr[s/2];
                   s/=2;}
       else break;
       }
       
       size++;
       }

void kopiec::delete_into(){
       tab[1] = tab[size];
       size--;
       int tmp = 1;
       while(tmp*2 <= size){
              if(tab[tmp] > tab[tmp*2] || tab[tmp] > tab[tmp*2+1])
              {
              if(tab[tmp*2] < tab[tmp*2+1] || tmp*2+1 > size){
                            
                           tab[tmp]=tab[tmp]^tab[tmp*2];
                           tab[tmp*2]=tab[tmp]^tab[tmp*2];
                           tab[tmp]=tab[tmp]^tab[tmp*2];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2];
                           node_nr[tmp*2]=node_nr[tmp]^node_nr[tmp*2];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2];
                            tmp=tmp*2;
                            
                            }
              else{
                   
                           tab[tmp]=tab[tmp]^tab[tmp*2+1];
                           tab[tmp*2+1]=tab[tmp]^tab[tmp*2+1];
                           tab[tmp]=tab[tmp]^tab[tmp*2+1];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2+1];
                           node_nr[tmp*2+1]=node_nr[tmp]^node_nr[tmp*2+1];
                           node_nr[tmp]=node_nr[tmp]^node_nr[tmp*2+1];
                   tmp=tmp*2+1;} 
              }
              else {QS[tmp]=false;break;}
       }
       if(QS[node_nr[1]]==false)delete_into();
       }
Komentarze
photo
0 # Władysław 2014-09-10 18:27
Powyższe rozwiązanie jest błędne - w grafie cyklicznym może nie zadziałać, a to z uwagi na permanentne usuwanie wierzchołków i wag z wektorów nie ma zastosowania kopiec do którego przecież można wsadzić wierzchołek więcej niż jeden raz w trakcie wykonywania algorytmu. Poprawne rozwiązanie ponownie wypełniałoby wektory (jeżeli są puste) dla wierzchołka wkładanego do kopca.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz