473,324 Members | 2,511 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

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 4485
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 thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: Ricardo Batista | last post by:
I need that someone help me. I need to program the dijkstra algorithm by object oriented. I'll send my code. #!/usr/bin/env python # -*- encoding: latin -*- NIL =
6
by: ThanhVu Nguyen | last post by:
Hi all, I need recommendation for a very fast shortest path algorithm. The edges are all directed, positive weights. Dijkstra shortest path will solve it just fine but the if the graph is not...
3
by: A_StClaire_ | last post by:
implemented Dijkstra's algorithm as follows. plz pour on the negative criticism cuz I know I have a ton to learn. oh, before you flame me regarding the language, my class was told to do this in...
3
by: Ook | last post by:
This is probably a bit OT, as I'm not looking for a c++ implementaiton of Dijkstra's algorithm, rather I'm just trying to understand it (is there a better place then here to ask this question?)....
1
by: arlef | last post by:
Can somebody please explain and provide pseudocode for the Dijkstra algorithm? I'm trying to implement the Dijkstra shortest path algorithm. However, I'm finding it extremely difficult to...
8
by: abhradwip | last post by:
I want to write a program which will find the shortest path between n no. of cities using dijkstra's algorithm ...... but could not do it..... i have written a program which will give the shortest...
1
Ganon11
by: Ganon11 | last post by:
Hey guys, I'm back, and with another FUN question! My latest homework asks this question: "Suppose all the edge weights in a graph are integers between 1 and |E|. How fast can Dijkstra's...
2
by: shashankbs | last post by:
Given a topology and a certain node X, find the shortest path tree with X as the root. * Input: a topology file similar to the following (which is a three-node ring) ...
1
by: Glenton | last post by:
Hi All Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm: #!/usr/bin/env python #This is meant to solve a maze with Dijkstra's...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.