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[b];

P[b] = P[a];

P[a] = temp;

G[P[a]].toPot = a;

G[P[b]].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[i].dist = INFTY;

G[i].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[u].dist G[v].dist + ps->nodeLabel) {

G[u].dist = G[v].dist + ps->nodeLabel;

bubbleUp(G[u].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