473,215 Members | 1,238 Online

# 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

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
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 4479
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

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
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() {
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
<snip>
Bart wrote:
>You can't say we
didn't warn you about that in earlier posts. Why don't you want to

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

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
<snip>
>Bart wrote:
>>You can't say we
didn't warn you about that in earlier posts. Why don't you want to

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 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: veera ravala | last post by: ServiceNow is a powerful cloud-based platform that offers a wide range of services to help organizations manage their workflows, operations, and IT services more efficiently. At its core, ServiceNow... 0 by: VivesProcSPL | last post by: Obviously, one of the original purposes of SQL is to make data query processing easy. The language uses many English-like terms and syntax in an effort to make it easy to learn, particularly for... 0 by: mar23 | last post by: Here's the situation. I have a form called frmDiceInventory with subform called subfrmDice. The subform's control source is linked to a query called qryDiceInventory. I've been trying to pick up the... 2 by: jimatqsi | last post by: The boss wants the word "CONFIDENTIAL" overlaying certain reports. He wants it large, slanted across the page, on every page, very light gray, outlined letters, not block letters. I thought Word Art... 2 by: isladogs | last post by: The next Access Europe meeting will be on Wednesday 7 Feb 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:30 (7.30PM). In this month's session, the creator of the excellent VBE... 0 by: fareedcanada | last post by: Hello I am trying to split number on their count. suppose i have 121314151617 (12cnt) then number should be split like 12,13,14,15,16,17 and if 11314151617 (11cnt) then should be split like... 0 by: stefan129 | last post by: Hey forum members, I'm exploring options for SSL certificates for multiple domains. Has anyone had experience with multi-domain SSL certificates? Any recommendations on reliable providers or specific... 0 by: egorbl4 | last post by: Скачал я git, хотел начать настройку, а там вылезло вот это Что это? Что мне с этим делать? ... 0 by: MeoLessi9 | last post by: I have VirtualBox installed on Windows 11 and now I would like to install Kali on a virtual machine. However, on the official website, I see two options: "Installer images" and "Virtual machines"....