468,289 Members | 1,853 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,289 developers. It's quick & easy.

Dijkstra's algorithm segfaults

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

Aug 31 '06 #1
9 4205
Josh Zenker wrote:
My code compiles in g++ without any errors or warnings. Unfortunately
it segfaults when it runs.
If you could post a compilable and complete version it would be much
easier (or even possible) to spot a bug. Possibly your
#include "Dijkstra.h"
is sufficient. Without a self-contained piece of code, it's very
difficult to tell.

Some tips:

1. Don't use raw pointers. Mysterious segfaults are just deserved when
doing this.
2. When using STL containers and iterators, ".at()" rather than
"operator[]" is a simple way to get range checking.
3. When using the GNU compiler, you can use the debug containers (as
described in the manual of libstdc++). Those check ranges even on iterators.
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.
It might be correct, but I can't tell what it is you are passing by
reference.

Jens
Aug 31 '06 #2

Josh Zenker wrote:
<snip>
My code compiles in g++ without any errors or warnings. Unfortunately
it segfaults when it runs.
<snip>

Well, it's pretty hard to tell because your code is obfuscated by
unclear data types and a rather messy use of pointers. You can't say we
didn't warn you about that in earlier posts. Why don't you want to
follow our advice and use standard containers?

Regards,
Bart.

Aug 31 '06 #3
Jens Theisen wrote:
If you could post a compilable and complete version it would be much
easier (or even possible) to spot a bug. Possibly your
#include "Dijkstra.h"

is sufficient. Without a self-contained piece of code, it's very
difficult to tell.
// Dijkstra.h
#ifndef DIJKSTRA_H_
#define DIJKSTRA_H_

// Node is an integer
typedef int Node;
// List is a pointer to Cell
typedef struct Cell *List;
struct Cell {
Node nodeName;
float nodeLabel;
List next;
};

// PotNode is also an integer
typedef int PotNode;
// maximum number of vertices in graph
const int MAX = 10;
typedef struct GraphElement {
float dist;
List successors;
PotNode toPot;
} Graph[MAX];

// array of graph nodes
typedef Node Pot[MAX + 1];

// swaps two nodes of partially ordered tree
void swap(PotNode, PotNode, Graph&, Pot&);

float priority(PotNode, Graph, Pot);

void bubbleUp(PotNode, Graph&, Pot&);

void bubbleDown(PotNode, Graph&, Pot&, int);

void initialize(Graph&, Pot&, int*);

// executes Dijkstra's algorithm
void Dijkstra(Graph&, Pot&, int*);

#endif

Bart wrote:
You can't say we
didn't warn you about that in earlier posts. Why don't you want to
follow our advice and use standard containers?
Perhaps I should have mentioned that this is an assignment for a course
I'm taking, and we're not permitted to use the STL. But you're right;
you did warn me.

Oh, I'll give you guys my second source file to make it compilable:

// Main3.cpp
#include <iostream>
#include "Dijkstra.h"
using namespace std;

int main() {
// cells of adjacency list
Cell c12;
c12.nodeName = 2;
c12.nodeLabel = 4.0;

Cell c13;
c13.nodeName = 3;
c13.nodeLabel = 1.0;

Cell c14;
c14.nodeName = 4;
c14.nodeLabel = 5.0;

Cell c15;
c15.nodeName = 5;
c15.nodeLabel = 8.0;

Cell c16;
c16.nodeName = 6;
c16.nodeLabel = 10.0;

Cell c32;
c32.nodeName = 2;
c32.nodeLabel = 2.0;

Cell c45;
c45.nodeName = 5;
c45.nodeLabel = 2.0;

Cell c56;
c56.nodeName = 6;
c56.nodeLabel = 1.0;

// adjacency list for vertex 1
Graph graph;
graph[0].successors = &c12;
c12.next = &c13;
c13.next = &c14;
c14.next = &c15;
c15.next = &c16;
c16.next = NULL;

// adjacency list for vertex 2
graph[1].successors = NULL;

// adjacency list for vertex 3
graph[2].successors = &c32;
c32.next = NULL;

// adjacency list for vertex 4
graph[3].successors = &c45;
c45.next = NULL;

// adjacency list for vertex 5
graph[4].successors = &c56;
c56.next = NULL;

// adjacency list for vertex 6
graph[5].successors = NULL;

// execute algorithm
Pot potNodes;
PotNode last;
Dijkstra(graph, potNodes, &last); /* seg fault */

return 0;
}

The directed graph I'm using for testing can be described as follows:

Edge Cost
---- ----
1->2 4
1->3 1
1->4 5
1->5 8
1->6 10
3->2 2
4->5 2
5->6 1

Does this help?

Best Regards,
Josh

Aug 31 '06 #4
Josh Zenker wrote:
Perhaps I should have mentioned that this is an assignment for a course
I'm taking,
:)
and we're not permitted to use the STL.
Appalling.
Oh, I'll give you guys my second source file to make it compilable:
The immediate problem is that you really have 10 nodes (you dijkstra is
looping 10 times), but only 6 of your nodes have their successor list
initialised. With

graph[6].successors = NULL;
graph[7].successors = NULL;
graph[8].successors = NULL;
graph[9].successors = NULL;

it stops segfaulting. The dists look vaguely sensible.

One note, even in the absence of STL:

- Give your structs constructors and initialise them on construction,
rather than at a later point with an initialise function. In particular,

PotNode child;
child = 2 * a;

is better written as

PotNode child = 2 * a;

Never let uninitialised data hanging around.

On debugging:

- One simple strategy is to make some debug prints. Write a function
that prints your successor list and call it within the loop. This gives
you a strong hint of what's going on, and what was last done before the
segfault.

- A debugger is good for quickly finding the point of segfault, though
it's not alsways exactly where the underlying problem is. gdb is the
debugger of your platform, but it's a bit cumbersome for beginners to
get in; try the debug print method first.

Jens
Aug 31 '06 #5
"Josh Zenker" <jz*****@gmail.comwrote in message
news:11**********************@i3g2000cwc.googlegro ups.com...
<snip>
Bart wrote:
>You can't say we
didn't warn you about that in earlier posts. Why don't you want to
follow our advice and use standard containers?

Perhaps I should have mentioned that this is an assignment for a course
I'm taking, and we're not permitted to use the STL. But you're right;
you did warn me.
Just because you're not allowed to use the STL doesn't mean that you can't
roll your own version of containers (from a student perspective, if people
don't specific their pathological restrictions precisely enough, take
advantage of it...they can hardly object when you're writing code that
demonstrates a reasonable understanding of the language). In this instance,
you're using lists and priority queues; they'd be much better off as classes
(preferably generic ones) rather than being interspersed with the rest of
the code. Separate your concerns! :)

HTH,
Stu

<snip>
Aug 31 '06 #6
Thanks, all. You've been quite helpful, and I will remember your
advice on future projects.

Best Regards,
Josh

Sep 1 '06 #7
Josh Zenker wrote:
typedef struct Cell *List;

typedef struct GraphElement {
float dist;
List successors;
PotNode toPot;
} Graph[MAX];

// array of graph nodes
typedef Node Pot[MAX + 1];
Please don't use pointer and array typedefs. They make the
code very confusing for others to read.

Sep 1 '06 #8
Old Wolf wrote:
Please don't use pointer and array typedefs. They make the
code very confusing for others to read.
Thanks for the tip. I'll avoid them in the future.

Sep 1 '06 #9
"Stuart Golodetz" <sg*******@dNiOaSl.PpAiMpPeLxE.AcSoEmwrote in message
news:AN******************************@pipex.net...
"Josh Zenker" <jz*****@gmail.comwrote in message
news:11**********************@i3g2000cwc.googlegro ups.com...
<snip>
>Bart wrote:
>>You can't say we
didn't warn you about that in earlier posts. Why don't you want to
follow our advice and use standard containers?

Perhaps I should have mentioned that this is an assignment for a course
I'm taking, and we're not permitted to use the STL. But you're right;
you did warn me.

Just because you're not allowed to use the STL doesn't mean that you can't
roll your own version of containers (from a student perspective, if people
don't specific
Oops, I meant "specify" :)
their pathological restrictions precisely enough, take advantage of
it...they can hardly object when you're writing code that demonstrates a
reasonable understanding of the language). In this instance, you're using
lists and priority queues; they'd be much better off as classes
(preferably generic ones) rather than being interspersed with the rest of
the code. Separate your concerns! :)

HTH,
Stu

<snip>

Sep 2 '06 #10

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

2 posts views Thread by Ricardo Batista | last post: by
6 posts views Thread by ThanhVu Nguyen | last post: by
3 posts views Thread by A_StClaire_ | last post: by
3 posts views Thread by Ook | last post: by
1 post views Thread by arlef | last post: by
2 posts views Thread by MrBee | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.