Witam. Otóż stworzyłem program wykonujący algorytm Dijsktry na utworzonych przeze mnie strukturach danych (macierz wag i lista krawędzi). Oryginalny algorytm - http://www.rafalnowak.pl/wiki/index.php?title=Algorytm_Dijkstry .
Mój program:
// dijstkra.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <conio.h>
#include <windows.h>
#include <limits.h>
#include <vector>
#include <set>
using namespace std;
double PCFreq = 0.0; __int64 CounterStart = 0; void StartCounter() { LARGE_INTEGER li; if(!QueryPerformanceFrequency(&li))
cout << "QueryPerformanceFrequency failed!\n"; PCFreq = double(li.QuadPart)/1000; QueryPerformanceCounter(&li); CounterStart = li.QuadPart; } double GetCounter() { LARGE_INTEGER li; QueryPerformanceCounter(&li); return double(li.QuadPart-CounterStart)/PCFreq; }
// do struktur danych
int** macierz;
int** lista_krawedzi;
int liczba_wierzcholkow; //n
int liczba_krawedzi; //m
// pomocnicze do algorytmu dijsktry
const int infty = 1000000000; // nieskonczonosc
vector< pair<int,int> > adj[100000]; // tworzy wektor par (pary wierzcholkow)
vector<int> waga; // tworzy wektor, w ktorym przechowywane beda dlugosci sciezek miedzy dwoma wierzcholkami
struct cmp
{
// czy a jest mniejsze od b
bool operator() (const int &a, const int &b)
{
if (waga[a] < waga[b]) return true;
if (waga[a] > waga[b]) return false;
return a<b;
}
};
set<int, cmp> kopiec; // ;-)
// tworzenie macierzy wag
void utworz_macierz_wag(int liczba_wierzcholkow, int liczba_krawedzi)
{
int przekatna=0;
int waga;
// utworzenie tablicy na macierz wag
macierz = new int* [liczba_wierzcholkow];
for (int i = 0; i < liczba_wierzcholkow; i++ )
{
macierz[i] = new int [liczba_wierzcholkow];
};
// wypełnienie macierzy zerami
for (int i=0; i<liczba_wierzcholkow; i++)
{
for (int j=0; j<liczba_wierzcholkow; j++)
{
macierz[i][j]=0;
if (i==j)
{
// przypisanie -1 na przekatnej macierzy
macierz[i][j]=-1;
}
}
}
//zapewnienie spojnosci grafu poprzez zrobienie polaczenie 1-2-3-4-... czyli wpisanie elementow nad przekatna
// graf spojny ale nieskierowany
for (int i=1; i<liczba_wierzcholkow; i++)
{
while (macierz[i-1][i]==0)
{
//macierz[i][i-1] = macierz[i-1][i] = (rand()%10)+1;
macierz[i-1][i] = (rand()%10)+1;
przekatna++;
}
}
int roznica=liczba_krawedzi-przekatna;
// uzupelnienie pozostalych pol
for (int i=0;i<liczba_wierzcholkow; i++)
{
for (int j=0; j<liczba_wierzcholkow; j++)
{
// wpisywanie wag do pol poza glowna przekatna i poza tymi gdzie jest -1
if ( macierz[i][j]==0 && roznica>0 )
{
srand(i+j);
waga=(rand()%10)+1;
//macierz[i][j]=macierz[j][i]=waga;
macierz[i][j]=waga;
// zabezpieczenie aby nie wpisac wiecej liczb niz krawedzi
roznica--;
}
}
}
}
///////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////
void konwerter_macierzy_do_listy ()
{
lista_krawedzi = new int*[liczba_krawedzi];
for(int i = 0; i < liczba_krawedzi; ++i)
{
lista_krawedzi[i] = new int[3];
}
int v1=0, v2=0;
int j2=0;
for (int i=0; i<liczba_wierzcholkow; ++i)
{
for (int j=j2; j<liczba_wierzcholkow; ++j)
{
if ((macierz[i][j] != 0) && (macierz[i][j] != -1))
{
lista_krawedzi[v1][v2] = i+1;
lista_krawedzi[v1][v2+1] = j+1;
lista_krawedzi[v1][v2+2] = macierz[i][j];
v1 += 1;
}
}
++j2;
}
};
////////////////////////////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////
void wyswietl_macierz_wag ()
{
for (int i=0; i<liczba_wierzcholkow; i++)
{
for (int j=0; j<liczba_wierzcholkow; j++)
{
cout << macierz [i][j];
cout << " ";
};
cout << "\n";
}
};
///////////////////////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////////////////////
void wyswietl_liste_krawedzi ()
{
for (int i=0; i<liczba_krawedzi; i++)
{
for (int j=0; j<3; j++)
{
cout << lista_krawedzi [i][j];
cout << " ";
};
cout << "\n";
};
};
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////////////////////////
void dijkstra(int source)
{
int v, u, c;
waga.clear(); // kasuje wektor
waga.resize(liczba_wierzcholkow, infty); // ustawia rozmiar wektora wag na liczbe wierzcholkow i wstawia wszedzie infty
waga[source] = 0; // waga zrodla - od niego zaczynamy algorytm
kopiec.clear(); // usuwa wszystkie elementy z kopca
for (int i=0; i<liczba_wierzcholkow; i++)
{
kopiec.insert(i); // wstawia element do zbioru (kopca)
}
while( !kopiec.empty() ) // dopoki w kopcu sa elementy
{
u = *(kopiec.begin()); // przypisuje wskaznik na poczatek zbioru (kopca)
kopiec.erase(kopiec.begin()); // usuwa element wskazywany przez wskaznik
for (int i=0; i<adj[u].size(); i++) // adj[u].size() - zwraca rozmiar zbioru
{
v = adj[u][i].first; // pobiera pierwszy wierzcholek
c = adj[u][i].second; // pobiera drugi wierzcholek
if (waga[u]+c < waga[v]) // relaksacja - jezeli obecna waga + waga drogi przez wierzcholek c jest mniejsza niz wartosc drogi z wierzcholka v
{
// znalezienie w kopcu wierzcholka v i jego usuniecie
kopiec.erase(kopiec.find(v));
// uaktualniamy wagę wierzchołka v
waga[v] = waga[u]+c;
// ponowne wstawienie wierzcholka v
kopiec.insert(v);
}
}
}
};
int main()
{
int pierwszy,drugi,waga1;
int zrodlo;
int ujscie;
cout << "Wprowadz liczbe wierzcholkow: ";
cin >> liczba_wierzcholkow;
cout << "\nWprowadz liczbe krawedzi: ";
cin >> liczba_krawedzi;
//utworzenie struktur danych do algorytmu
utworz_macierz_wag(liczba_wierzcholkow, liczba_krawedzi);
konwerter_macierzy_do_listy();
/*
// dla listy krawedzi - na razie wylaczone
for (int i=0; i<liczba_krawedzi; i++)
{
pierwszy=lista_krawedzi[i][0];
drugi=lista_krawedzi[i][1];
waga1=lista_krawedzi[i][2];
//cin >> a >> b >> c; // c = koszt krawędzi od a do b
adj[pierwszy].push_back( pair<int,int>(drugi,waga1) ); //
};
*/
for (int i=0; i<liczba_wierzcholkow; i++)
{
for (int j=0; j<liczba_wierzcholkow; j++)
{
if ((macierz[i][j]!=-1) && (macierz[i][j]!=0))
{
pierwszy=i+1;
drugi=j+1;
waga1=macierz[i][j];
adj[pierwszy].push_back( pair<int,int>(drugi,waga1) );
}
}
}
wyswietl_macierz_wag();
wyswietl_liste_krawedzi();
cout << "Wprowadz zrodlo (wierzcholek poczatkowy): ";
cin >> zrodlo;
cout << "\nWprowadz ujscie (wierzcholek, do ktorego chcesz dojsc: ";
cin >> ujscie; // s - źródło, t - wierzchołek, do którego najkrótszej odległości szukamy
// wykonanie wlasciwej czesci algorytmu
dijkstra(zrodlo); // alg. Dijkstry wypełni całą tablicę waga[..] najkrótszymi odległościami
cout << "Najkrotsza droga z wierzcholka " << zrodlo << " do wierzcholka " << ujscie << " wynosi: " << waga[ujscie];
getch();
return 0;
}
W MS Visual wywala mi błąd vector subscript out of range, a w debugerze wskazuje na poniższy fragment kodu w bibliotece vector.
W Dev C++ natomiast pokazuje tylko segmentation fault.
#if _HAS_ITERATOR_DEBUGGING
if (size() <= _Pos)
{
_DEBUG_ERROR("vector subscript out of range");
_SCL_SECURE_OUT_OF_RANGE;
}
Nie wiem czy problem leży w samym algorytmie, czy w implementacji którejś ze struktur danych w moim programie. Mam nadzieję, że znajdzie się ktoś, kto pomoże mi rozwiązać ten problem.