?
Solved

Something funny is happening need help

Posted on 2002-05-01
3
Medium Priority
?
160 Views
Last Modified: 2010-04-02
I am trying to implement dijkstra's algrithm and this is the code. for some reason it seems to go into infinity loop. it doesn't even excute the cout statemtents.

First initialization of the matrix doesn't work . it prints garbage values in the last line.

It does not execute the cout statement cout <<"\n"<< "Yahoo";

I have been cracking my head for hours together. I hope some body can just help me out. I am trying to run this code on GNU/linux using g++. my skills of debugging with gdb are close to non-existant.

regards
bsd_linux

the code is here

include <iostream.h>
#define  HIGH 100000
#define  max 7
#define  start 2

int w[max][max];

// Declaring 2 global functions that we need to use later.

int least_weight(int weight[], int queue[], int *end);

void rearrange(int prev_node, int prev[], int w[max][max], int weight[]);

int no_of_nodes=6;

int main(void)
{
/* we have to implement a priority queue of the adjusting and calculating the
 * neighbours. Now the weight matrix is already defined before. So we need to
 * just access the matrix and then adjust the weight.
 */
       
/*      int weight[7][7]={{-1,-1,-1,-1,-1,-1,-1},
                          { -1,0,1,-1,-1,1,-1},
                          {-1,1,0,2,-1,-1,1},
                          {-1,-1,2,0,1,-1,1},
                          {-1,-1,-1,1,0,2,-1},
                          {-1,1,-1,-1,2,0,-1},
                          {-1,-1,1,1,-1,-1,0}};*/
        int i=0,j=0;

        cout <<"\n" << " I am in the main ";

        for(i=0;i<max;i++)
        {
                w[0][i]=-1;
                w[i][0]=-1;
        }
        w[1][3]=w[1][4]=w[1][6]=-1;
        w[2][4]=w[2][5]=-1;
        w[3][1]=w[3][5]=-1;
        w[4][1]=w[4][2]=w[4][6]=-1;
        w[5][2]=w[5][3]=w[5][6]=-1;
        w[6][1]=w[6][5]=w[6][4]=-1;
        w[1][1]=w[2][2]=w[3][3]=w[4][4]=w[5][5]=w[6][6]=0;
        w[1][2]=w[1][5]=w[2][1]=w[2][6]=w[3][4]=w[4][3]=w[6][2]=w[6][3]=w[5][1]=1;
        w[3][6]=1; w[2][3]=w[3][2]=w[4][5]=w[5][4]=2;
/*
        for(i=0;i<7;i++)
        {
                cout <<"\n";
                for(j=0;j<7;j++)
                        cout<<"\t"<<w[i][j];
        }
*/
/* 1) No of nodes is got from the main fn. It has to be passed as a parameter.
 * eg. the fn is to invoked as di(int no_of_nodes).
 *
 * 2) 3 arrays would be needed. One to hold temporary weight and another the
 * previous node. Indexing is done from 1 to make it easier to refer to the
 * values. Eg. Prev[9]=8 means that to get to the shortest path to node 9
 * would be through node 8. The third would be the queue.
 *
 * 3) We first initialize the weight array to hold the highest weight possible.
 * and the previous node array is initialized to all zero's.
 */
 
int prev[max], weight[max],queue[max];

cout <<"\n"<< " I am going to initiazile the prev and weight matrix";
for(j=0;j<max;j++)
{
        cout<<"\n I am in the loop and the value of j is "<<j;
        weight[j] = HIGH;
        prev[j] = 0;
}

cout<<"\n"<<" I have intialized both the prev and the weight matrix";

/* However the weight of the start node to itself is zero and there is no
 * previous node to the start node. So we initialize prev node of the
 * start node to be itself.
 */

cout<< "\n" <<" Yahooo";

weight[start]=0;
prev[start]=start;

/* The number of the nodes in the queue would be the number of nodes created
 * The nodes enter the queue as when they are created.
 */

int end_of_queue = no_of_nodes - 1;
for(int i=0;i<no_of_nodes;i++)
          queue[i]=i+1;

/* Now we attempt to process the elements in the queue */

while(end_of_queue!=-1)
{
        int prev_node = least_weight(weight, queue, &end_of_queue);
        rearrange(prev_node, prev, w, weight);
}
for(int k =1;k<=no_of_nodes;k++)
cout<<"\n"<<prev[k];
}

// Now we define the functions

/* In a priority queue we assume the first element to be the least element
 * until we find a lesser value later on in the queue.
 */

int least_weight(int weight[], int queue[], int *end_of_queue)
{
  int id_of_node = 0;
  int temp_min_weight = weight[queue[0]];
  int temp = 0;
  for(int loop=1;loop<= *end_of_queue; loop++)
  {
          if(weight[queue[loop]] < temp_min_weight)
          {
                  temp_min_weight = weight[queue[loop]];
                  temp = loop;
          }
  }

// We have now the min_weight_node in the queue.

id_of_node = queue[temp];

// Now we move elements in the queue

for(int loop2=temp; loop2< *end_of_queue; loop2++)
        queue[loop2] = queue[loop2+1];

// The length of the queue is reduced by one

*end_of_queue--;

return id_of_node;
}

/* Now we try to estimate which one should be the previous node that would help
 * in finding out the path to those nodes that are not directly connected.
 */

void rearrange(int prev_node, int prev[], int w[max][max], int weight[])
{
        int node;
        int temp_min_weight=0;
        int node_weight=0;
        int loop, loop2;        

        for( loop=1; loop<=no_of_nodes;loop++)
        {
// if the weight is less than 0 means that there is no link. If it is zero
// means that it is loop to itself.
               
                if(w[prev_node][loop]<=0)
                        continue;
                node = loop;
                temp_min_weight = weight[loop];
                node_weight = weight[loop];

// Now we search for the the node of the least weight. For that we calculate
// the weight and look for the least.

                for(loop2=1; loop2<=no_of_nodes; loop2++)
                {
                        if(w[loop2][node]<=0)
                                continue;
                        node_weight = weight[loop2] + w[loop2][node];
                        if(node_weight<temp_min_weight)
                        {
                                temp_min_weight = node_weight;
                                 prev[node] = loop2;
                        }
                }
                weight[node] = temp_min_weight;
        }
}

0
Comment
Question by:bsd_linux
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
3 Comments
 
LVL 16

Accepted Solution

by:
Peter Kwan earned 1080 total points
ID: 6983010
The reason for infinity loop because the precedence of the unary operator * is the same as --. However, the associativity is from right to left. Therefore, the statement *end_of_queue-- will execute -- first, and then deference the result.

To solve your problem, you need to add parenthesis, such as (*end_of_queue)--

Hope this helps.
0
 
LVL 22

Expert Comment

by:ambience
ID: 6983017
>> It does not execute the cout statement cout <<"\n"<< "Yahoo";

It does, only that cout is a buffered output stream so you need to call

cout.flush()
or
cout << endl;

that should flush all the data to output.


>> *end_of_queue--;

Thats evil, should be

(*end_of_queue)--;

and should take care of infinite loop.
0
 

Author Comment

by:bsd_linux
ID: 6983832
Whoa!! A greasy measly pointer. Bah! thanks folks. I really appreciate it.

regards
bsd_linux
0

Featured Post

On Demand Webinar: Networking for the Cloud Era

Did you know SD-WANs can improve network connectivity? Check out this webinar to learn how an SD-WAN simplified, one-click tool can help you migrate and manage data in the cloud.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question