J
Josh Zenker
I've been working on an implementation of Dijkstra's algorithm on and
off for the past few days. I thought I was close to being finished,
but clearly I've done something wrong. I'm not a very experienced
programmer, so please be patient.
My code compiles in g++ without any errors or warnings. Unfortunately
it segfaults when it runs. I tried adding some outputs to the console
throughout the "Dijkstra" function but wasn't able to pinpoint the
problem. All I discovered was that the segfault occurs sometime after
the sixth vertex of a six-vertex digraph is visited in the inner while
loop of the Dijkstra function-which is pretty much where you'd expect
a segfault to occur if one was going to occur at all; and the value of
u is a large positive integer during the last iteration. Maybe, if I
post the code below, someone will be able to spot my mistake...? I've
made an effort to add comments where a little extra explanation may be
necessary. I don't mind clarifying anything that's still unclear,
though.
// Dijkstra.cpp
#include <iostream>
#include "Dijkstra.h"
using namespace std;
// swaps two nodes
void swap(PotNode a, PotNode b, Graph &G, Pot &P) {
Node temp; /* Node and PotNode are integers */
temp = P;
P = P[a];
P[a] = temp;
G[P[a]].toPot = a;
G[P].toPot = b;
}
// returns the priority of a partially ordered tree node
float priority(PotNode a, Graph G, Pot P) {
return G[P[a]].dist;
}
// pushes a new element up until the tree is partially ordered again
void bubbleUp(PotNode a, Graph &G, Pot &P) {
if ((a > 1) &&
(priority(a, G, P) < priority(a/2, G, P))) {
swap(a, a/2, G, P);
bubbleUp(a/2, G, P);
}
}
void bubbleDown(PotNode a, Graph &G, Pot &P, int last) {
PotNode child;
child = 2 * a;
if (child < last &&
priority(child+1, G, P) < priority(child, G, P))
++child;
if (child <= last &&
priority(a, G, P) > priority(child, G, P)) {
swap(a, child, G, P);
bubbleDown(child, G, P, last);
}
}
// arbitrarily large value
const int INFTY = 100;
// create starting condition
void initialize(Graph &G, Pot &P, int *pLast) {
for (int i = 0; i < MAX; i++) {
G.dist = INFTY;
G.toPot = i + 1;
P[i+1] = i;
}
G[0].dist = 0;
(*pLast) = MAX;
}
// execute Dijkstra's algorithm
void Dijkstra(Graph &G, Pot &P, int *pLast) {
Node u, v; /* v is the node we select */
List ps; /* ps traverses the list of v's successors */
initialize(G, P, pLast);
while ((*pLast) > 1) {
v = P[1];
swap(1, *pLast, G, P);
--(*pLast);
bubbleDown(1, G, P, *pLast);
ps = G[v].successors;
while (ps != NULL) {
u = ps->nodeName;
if (G.dist > G[v].dist + ps->nodeLabel) {
G.dist = G[v].dist + ps->nodeLabel;
bubbleUp(G.toPot, G, P);
}
ps = ps->next;
}
}
}
I'm also not sure I'm making the correct use of the reference operator
('&') in this code. I'd appreciate any suggestions you may have.
Best Regards,
Josh
off for the past few days. I thought I was close to being finished,
but clearly I've done something wrong. I'm not a very experienced
programmer, so please be patient.
My code compiles in g++ without any errors or warnings. Unfortunately
it segfaults when it runs. I tried adding some outputs to the console
throughout the "Dijkstra" function but wasn't able to pinpoint the
problem. All I discovered was that the segfault occurs sometime after
the sixth vertex of a six-vertex digraph is visited in the inner while
loop of the Dijkstra function-which is pretty much where you'd expect
a segfault to occur if one was going to occur at all; and the value of
u is a large positive integer during the last iteration. Maybe, if I
post the code below, someone will be able to spot my mistake...? I've
made an effort to add comments where a little extra explanation may be
necessary. I don't mind clarifying anything that's still unclear,
though.
// Dijkstra.cpp
#include <iostream>
#include "Dijkstra.h"
using namespace std;
// swaps two nodes
void swap(PotNode a, PotNode b, Graph &G, Pot &P) {
Node temp; /* Node and PotNode are integers */
temp = P;
P = P[a];
P[a] = temp;
G[P[a]].toPot = a;
G[P].toPot = b;
}
// returns the priority of a partially ordered tree node
float priority(PotNode a, Graph G, Pot P) {
return G[P[a]].dist;
}
// pushes a new element up until the tree is partially ordered again
void bubbleUp(PotNode a, Graph &G, Pot &P) {
if ((a > 1) &&
(priority(a, G, P) < priority(a/2, G, P))) {
swap(a, a/2, G, P);
bubbleUp(a/2, G, P);
}
}
void bubbleDown(PotNode a, Graph &G, Pot &P, int last) {
PotNode child;
child = 2 * a;
if (child < last &&
priority(child+1, G, P) < priority(child, G, P))
++child;
if (child <= last &&
priority(a, G, P) > priority(child, G, P)) {
swap(a, child, G, P);
bubbleDown(child, G, P, last);
}
}
// arbitrarily large value
const int INFTY = 100;
// create starting condition
void initialize(Graph &G, Pot &P, int *pLast) {
for (int i = 0; i < MAX; i++) {
G.dist = INFTY;
G.toPot = i + 1;
P[i+1] = i;
}
G[0].dist = 0;
(*pLast) = MAX;
}
// execute Dijkstra's algorithm
void Dijkstra(Graph &G, Pot &P, int *pLast) {
Node u, v; /* v is the node we select */
List ps; /* ps traverses the list of v's successors */
initialize(G, P, pLast);
while ((*pLast) > 1) {
v = P[1];
swap(1, *pLast, G, P);
--(*pLast);
bubbleDown(1, G, P, *pLast);
ps = G[v].successors;
while (ps != NULL) {
u = ps->nodeName;
if (G.dist > G[v].dist + ps->nodeLabel) {
G.dist = G[v].dist + ps->nodeLabel;
bubbleUp(G.toPot, G, P);
}
ps = ps->next;
}
}
}
I'm also not sure I'm making the correct use of the reference operator
('&') in this code. I'd appreciate any suggestions you may have.
Best Regards,
Josh
