Ask help for Dijkstra's algorithm in C++

Unknown

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

Head file and part of .CPP are provided.

Please help me to finish the lab5.cpp.

LAB5.CPP

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

#include

#include

#include "stack.cpp"

const HUGE = 1000;

typedef int adjacent[20][20];

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

void Load_Graph( adjacent adj, int & size );

void Dijkstra( adjacent adj, int size );

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

using namespace std; //introduces namespace std

int main( void )

{

adjacent adj;

int graph_size;



Load_Graph( adj, graph_size );

Dijkstra( adj, graph_size );

return 0;

}

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

void Load_Graph( adjacent adj, int & size ) {

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;

}

}

void Dijkstra ( adjacent adj, int size ) {

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

}

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

HEAD FILE

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() {

return top == NULL;

}

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

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.

Please reply to william886@hotmail.com

Unknown

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.

Based on your Load_Graph, it seems like you have a weighted adjacency list in the two-dimensional array generally referred to in all of your functions as adj.

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.