Я пытаюсь реализовать кратчайший путь Дейкста, используя минимальную кучу, но у меня возникают проблемы с некорректным обновлением поля расстояния после выполнения релаксации. Я также получаю ошибку сегментации при попытке некоторых тестовых случаев, и я не уверен, почему. При нажатии R программа должна прочитать график и построить список смежных ребер графа. Список смежности ребер - это массив (индексируемый вершинами) списков с сингулярной связью, где список в соответствии с узлом v обозначает исходящих соседей узла v. Он построен с использованием graphinput.txt и функции buildGraph, которую я обрисовал в общих чертах на дно; Входной текстовый файл является следующим, где 25 и 50 - число вершин и ребер соответственно:
25 50
1 1 3
1 6 2
1 2 7
1 11 1
6 11 3
11 6 2
7 1 4
11 12 4
2 7 10
7 2 10
16 12 7
21 16 4
21 22 1
22 21 2
3 1 5
18 21 1
18 22 3
22 23 5
12 18 8
18 12 7
7 13 3
12 8 2
2 8 1
2 9 3
4 3 4
5 4 7
10 5 3
4 10 10
14 4 15
15 10 8
10 15 6
10 15 7
8 13 2
8 9 1
9 9 4
13 18 1
23 23 7
23 24 4
23 14 1
24 13 9
14 19 1
19 24 1
15 14 2
14 20 16
14 25 30
20 25 15
24 25 26
23 25 8
25 15 2
17 16 13
При чтении FST 1 программа должна распечатать длину кратчайшего пути от узла s к узлу т. При чтении FST 0 программа должна вывести кратчайший путь от узла s к узлу t. Если узлы не достижимы, это выдает ошибку. Вот структуры, которые я использую, где d в ELEMENT - это расстояние, p - это родитель, а key - это значение. В куче H - это массив типа ELEMENT с индексом от 0 до емкости. Это мои структуры кучи:
struct ELEMENT{ //declaring the element struct with a key
int key;
int d;
int p;
};
struct HEAP{ //declaring the heap struct with a capacity size and a pointer h
int capacity;
int size;
ELEMENT *h;
};
Мои структуры графиков:
struct GRAPH{
int v;
int e;
struct ELEMENT *h;
struct LIST** A;
};
struct LIST{
int neighbor;
int weight;
struct LIST* next;
};
Затем я использую следующее функции кучи:
ELEMENT deleteMin(GRAPH *g){
ELEMENT trueMin;
if(g->v >=1){ //proceeds only if the heap size is greater than or equal to 1
trueMin = g->h[1]; //initializing element variable for the min that gets deleted
}
if(g->v < 1){ //if the heap is empty print this error
cout << "Error: heap empty" << endl;
}
else{
ELEMENT min = g->h[1];
g->h[1] = g->h[g->v];
g->v--;
minHeapify(g,g->h[1].key);
trueMin = min; //else min is equal to first element, is swapped with the last, size is decreased, and minheapfiy is called
}
return trueMin;
}
void decreaseKey(GRAPH *g, int index, int value){
if(index > g->v || index < 1){ //if the index is greater than the size of the index is less than 1 print error
//cout<< "Error: invalid index" << endl;
return;
}
if(value > g->h[index].d){// if the value trying to be increased is greater than the current index value print error
//cout << "Error: new key is bigger than current key" << endl;
return;
}
else{
g->h[index].d = value; //else set the index equal to the key value and swap the parent until the parent has a less value
while( index > 1 && g->h[parent(index)].d > g->h[index].d){
swap(&g->h[index], &g->h[parent(index)]);
index = parent(index);
}
}
}
void minHeapify(GRAPH *g, int i){ //minHeapify algorithm to maintain min heap property where the parent of any given node is always less than its children
int smallest = 0;
int l = left(i);
int r = right(i);
if(l <= g->v && g->h[l].d < g->h[i].d){ //checking if children exist
smallest = l;//setting the smallest equal to left if the left is smaller
} else{
smallest = i;
}
if(r <= g->v && g->h[r].d < g->h[smallest].d){ //checking if children exist
smallest = r;//setting the smallest equal to right if the right is smaller
}
if(smallest != i){ //if the smallest is not equal to i entered by user then swap and minHeapify function
int temp = g->h[i].d;
int temp1 = g->h[i].key;
int temp2 = g->h[i].p;
g->h[i].key = g->h[smallest].key;
g->h[i].d = g->h[smallest].d;
g->h[i].p = g->h[smallest].p;
g->h[smallest].key = temp;
g->h[smallest].d = temp1;
g->h[smallest].p = temp2;
minHeapify(g, smallest);
}
}
void buildHeap(GRAPH *g){
for(int i = floor(g->v/2); i >= 1; i--){
minHeapify(g, i); //performing the buildHeap operation
}
}
int parent(int i){
return floor(i/2);//parent function to return parent node
}
int left(int i){//left function to return left node
return 2 * i;
}
int right(int i){//right function to return right node
return (2 * i + 1);
}
void swap(ELEMENT *a, ELEMENT *b){ //swaps elements using pointers and a temp variable
ELEMENT temp;
temp = *a;
*a = *b;
*b = temp;
return;
}
Для своего графика я использую следующие функции:
GRAPH* initializeGraph(){ //initializing the graph
GRAPH *g = new GRAPH;
g->v=0;
g->h=nullptr;
g->A=nullptr;
g->e=0;
return g;
}
void initializeSingleSource(GRAPH *g, int s)
{
for (int i = 1; i <= g->v; i++)
{
g->h[i].d = INT_MAX - 1000; //setting all the distances to infinity
g->h[i].p = -1; //setting parent field to nonexistent
}
g->h[s].d = 0; //setting the source distance to 0 to start the algorithm
//g->h = new ELEMENT[g->v + 1];
}
void relax(GRAPH *g, int u, int v, int w)
{
int uindex = 0; //variables to search for the index of u and v
int vindex = 0;
for(int i = 1; i <= g->v; i++){ //searching
if(g->h[i].key == u){
uindex = i;
break;
}
}
for(int i = 1; i <= g->v; i++){ //searching
if(g->h[i].key == v){
vindex = i;
break;
}
}
if (g->h[vindex].d > g->h[uindex].d + w) //performing relaxation on indices
{
g->h[vindex].d = g->h[uindex].d + w;
g->h[vindex].p = u;
decreaseKey(g, g->h[vindex].d, w + g->h[uindex].d); //calling decreasekey to maintain minheap property
}
}
void Dijkstra(GRAPH *g, int s, int t, int flag) //s and t are source and target nodes flag determines what to print
{
g->h = new ELEMENT[g->v + 1];
for (int i = 1; i <= g->v; i++) { //setting i
g->h[i].key = i;
}
initializeSingleSource(g,s); //setting initial fields
std::vector<ELEMENT> S; //vector to hold extracted min elements
buildHeap(g); //calling buildheap on g
//cout << g->h[s].d << endl;
while (g->v > 0)
{
ELEMENT u = deleteMin(g); //extracting min
S.push_back(u);
LIST *temp = g->A[u.key]; //pointer for adjacency list
while(temp){
relax(g, u.key,temp->neighbor,temp->weight); //performing relaxation
cout << "update " << temp->neighbor << " distance to " << g->h[temp->neighbor].d << endl; //for debugging purposes
temp = temp->next;
}
}
for(int i = 0; i < S.size(); i++){
if(S[i].key == t){
if(S[i].d == INT_MAX - 1000){ //if distance is still infinity after relaxation then error
std::cout << "Error: node " << t << " not reachable from " << s << std::endl;
}
else{
if(flag == 1){ //if flag is 1 then output the length of the shortest path
std::cout << "LENGTH: " << S[i].d << std::endl;
}
// if (flag == 0 && s == t){
// cout << "PATH: " << s << endl; //wrote this to get more test cases passing without solving real problem
//}
else if(flag == 0){ //if 0 output the path for shortest distance
vector<int> path;
int temp = t;
while(temp != -1){ //while temp os not -1 loop through vector
for(int i = 0; i < S.size(); i++){
if(S[i].key == temp){
path.insert(path.begin(), temp); //insert path until -1
temp = S[i].p;
break;
}
}
}
std::cout << "PATH: ";
for(int i = 0; i < S.size(); i++){
std::cout << path[i]; //printing path as comma separated list
if(i < path.size() - 1){
std::cout << ", ";
}
}
std::cout << std::endl;
}
}
}
}
delete g->h;
}
void buildGraph(GRAPH *g)
{
//GRAPH *g = new GRAPH;
ifstream myfile("Ginput.txt"); //building the adjacency list
int v1 = 0, e1 = 0;
myfile >> v1 >> e1;
if (v1 == 0 || e1 == 0){
std::cout << "Errorr: unable to open file " << std::endl;
}
g->v = v1;
g->e = e1;
g->h = nullptr;
g->A = new LIST *[v1 + 1];
for (int i = 1; i <= v1; i++)
{
g->A[i] = NULL;
}
int u,v,w;
while (myfile >> u >> v >> w)
{
LIST *temp = new LIST;
temp->neighbor = v;
temp->weight = w;
temp->next = NULL;
if (g->A[u] == NULL)
{
g->A[u] = temp;
}
else
{
temp->next = g->A[u];
g->A[u] = temp;
}
}
myfile.close();
}
И это пример вывода, который я получаю, когда печатаю, что релакс делает в моем в то время как l oop функции dijkstra.
R
COMMAND: R
F 1 1 1
COMMAND: F 1 1 1
update 11 distance to 32712
update 2 distance to 32718
update 6 distance to 32713
update 1 distance to 2147482647
update 15 distance to 32713
update 25 distance to 2147482647
update 13 distance to 32720
update 25 distance to 2147482647
update 14 distance to 32712
update 24 distance to 2147482647
update 23 distance to 2147482647
update 23 distance to 2147482647
update 21 distance to 2147482647
update 22 distance to 2147482647
update 16 distance to 32715
update 25 distance to 2147482647
update 24 distance to 2147482647
update 12 distance to 32718
update 22 distance to 2147482647
update 21 distance to 2147482647
update 16 distance to 32715
update 12 distance to 32718
update 14 distance to 32712
update 10 distance to 32719
update 25 distance to 2147482647
update 20 distance to 2147482647
update 19 distance to 2147482647
update 4 distance to 32726
update 18 distance to 2147482647
update 8 distance to 32713
update 18 distance to 2147482647
update 12 distance to 32718
update 6 distance to 32713
update 15 distance to 32713
update 15 distance to 32713
update 5 distance to 32714
update 9 distance to 2147482647
update 9 distance to 2147482647
update 13 distance to 32720
update 13 distance to 32720
update 2 distance to 32718
update 1 distance to 32713
update 11 distance to 32712
update 4 distance to 32726
update 10 distance to 32719
update 3 distance to 2147482647
update 1 distance to 32718
update 9 distance to 2147482647
update 8 distance to 32713
update 7 distance to 2147482647
LENGTH: 0
F 6 11 0
COMMAND: F 6 11 0
update 11 distance to 32714
update 15 distance to 32713
update 25 distance to 2147482647
update 13 distance to 32720
update 25 distance to 2147482647
update 14 distance to 32712
update 24 distance to 2147482647
update 23 distance to 2147482647
update 23 distance to 2147482647
update 21 distance to 2147482647
update 22 distance to 2147482647
update 16 distance to 32715
update 25 distance to 2147482647
update 24 distance to 2147482647
update 12 distance to 32718
update 22 distance to 2147482647
update 21 distance to 2147482647
update 16 distance to 32715
update 12 distance to 32718
update 14 distance to 32712
update 10 distance to 32719
update 25 distance to 2147482647
update 20 distance to 2147482647
update 19 distance to 2147482647
update 4 distance to 32726
update 18 distance to 2147482647
update 8 distance to 32713
update 18 distance to 2147482647
update 12 distance to 32718
update 6 distance to 3
update 15 distance to 32713
update 15 distance to 32713
update 5 distance to 32714
update 9 distance to 2147482647
update 9 distance to 2147482647
update 13 distance to 32720
Segmentation fault (core dumped)
Это часть основного, где я использую функцию Dijkstra:
case 'F':
printf("COMMAND: %c %d %d %d\n",c ,f, i, v);
if (!g) {
std::cout << "Error: graph not initialized" << std::endl;
break;
}
if(f > 25 || f < 1 || i > 25 || i < 1){
if (v != 0 && v != 1){
std::cout << "Error: one or more invalid nodes" << std::endl;
std::cout << "Error: invalid flag value" << std::endl;
break;
}
}
if(f > 25 || f < 1 || i > 25 || i < 1){
std::cout << "Error: one or more invalid nodes" << std::endl;
break;
}
if (v != 0 && v != 1) {
std::cout << "Error: invalid flag value" << std::endl;
break;
}
Dijkstra(g,f,i,v);
buildGraph(g); //called to avoid errors when extractmin is called to decrease graph size
break;
Если кто-нибудь мог бы сказать мне, что я делаю неправильно Я был бы очень признателен.