# Ask help for Dijkstra's algorithm in C++

Help! I am working on a dijkstra's algorithm with C++.

Head file and part of .CPP are provided.

LAB5.CPP

------------------------------------------------------

#include

#include

#include "stack.cpp"

const HUGE = 1000;

//----------------------------------------------------

//----------------------------------------------------

using namespace std; //introduces namespace std

int main( void )

{

int graph_size;

return 0;

}

//----------------------------------------------------

char * filename = "";

ifstream input; //input file name: inside of the program

cout << "Enter the name of the graph file: ";<br>
cin.getline( filename, 80 );

input.open( filename );

int edges;

input >> size >> edges;

int i, j;

for ( i = 0; i < size; i++ )

for ( j = 0; j < size; j++ )

adj[ i ][ j ] = 0;

int first, second, weight;

for ( i = 1; i <= edges; i++ ) {<br>
input >> first >> second >> weight;

if ( weight < 0 )

weight = -weight;

adj[ first ][ second ] = weight;

adj[ second ][ first ] = weight;

}

}

//..........

}

------------------------------------------------------

template

class Stack {

public:

Stack();

void Push( T item );

T Pop();

T Top();

bool Empty();

private:

struct node {

T data;

node * next;

node( T dat, node * nex )

{ data = dat; next = nex; }

} * top;

};

-------------------------------------------------------

STACK.CPP

#include "stack.h"

template

Stack::Stack() {

top = NULL;

}

template

void Stack::Push( T item ) {

top = new node ( item, top );

}

template

T Stack::Pop() {

T item = top->data;

node * temp = top;

top = top->next;

delete temp;

return item;

}

template

T Stack::Top() {

return (top->data);

}

template

bool Stack::Empty() {

}

-------------------------------------------------------

A sample problem

10 14

0 1 4

0 2 1

1 2 10

1 3 1

2 3 5

2 8 9

3 6 3

4 5 2

6 4 1

6 5 3

6 7 7

6 8 1

8 9 2

9 7 1

Thanks a lot.

• You haven't really explained what you want answered. Most of us are marginally ethical enough or busy enough not to write the whole thing for you. From this, you want to produce a shortest path tree from a given node (root) to every other node. You may not be interested in the exact tree, but just interested in the distances from the root.

Initially, only the root is in the 'shortest tree', and its immediate neighbours' distance-to-root are known. Also, if you're keeping track of the shortest-tree, the parent of the neighbours is the root node. All other parents are set to an illegal value, and all other distances are set to some value indicating 'infinite'. Djikstra's algorithm is layed out as follows (ignore the back-quote symbols):

while not all the nodes are in the shortest-path-tree

``find the node k that isn't yet in the shortest-path-tree that has the shortest path to the root so far

``Add node k to the shortest-path-tree.

``For each of the neighbour nodes n of node k that is not already in the shortest-path-tree:

````Compute node n's distance-to-root via node k.

````If the computed distance is shorter than n's current shortest distance, then set n's current shortest distance to the computed distance. Also, if this condition is met, and you're interested in the actual shortest-path-tree, set the parent of node n to be node k.

If, when you go to find the smallest-path neighbour, the smallest path is infinite, then you've got a disconnected graph.

Most of this you've probably got from your professor. To get anything else from me, you'll have to ask less vague questions. 