asked on

Dijkstra's Algorithm implementation

Hello Experts,

I am having a real dilly of a pickle here with implementing this algorithm. I understand the basic concept on how it tries to find the shortest path from point a to c with the least amount of weight, but I believe I am coding more than I need to.

If some one could take a peek and show me what i'm doing wrong I would appreciate it.

Stuff to know:
argument s = = 0
size == 10
adj_matrix[s][u] = sees if points are adjacent
distance[s][u] = tells you the weight of edge
precede[s][u] = suppose to move to previous node

all() = function to test if array contains all correct bools = in this case 'false'

If I didn't make this clear enough let me know and thanks for your help!

**************************************************************
void graph::short_path_graph(int s)
{
      bool * permanent;
      permanent = new bool [size];

      for(int x = 0; x < size; x++)
      {
            permanent[x] = false;
      }


      for(int i = 1; i < size; i++)
      {
            distance[s][i] = INT_MAX;
      }


      distance[s][s] = 0;

      while(!all(permanent))
      {
            int u = 0;
            int v = 0;

            for(int i = 1; i < size; ++i)
            {
                  for(int y = 0; y < size; y++)
                  {
                        if(adj_matrix[s][i] && adj_matrix[s][y])
                        {
                              if(distance[s][i] < distance[s][y] && !permanent[s])
                              {
                                    v = distance[s][i];
                                    y++;
                              }

                        }

                  }
            }


            permanent[v] = true;

            for(u = 0; u < size; ++u)
            {
                  if(adj_matrix[v][u])
                  {
                        if(distance[s][u] > distance[s][v] + distance[v][u])
                        {
                              distance[s][u] = distance[s][v] + distance[v][u];

                              precede[s][u] = v;

                        }

                  }

            }


      }

}

***************************************

ASKER CERTIFIED SOLUTION

itsmeandnobodyelse

membership

This solution is only available to members.

To access this solution, you must be a member of Experts Exchange.

Start Free Trial

nothing8171

ASKER

Could you post the implementation of all() ?
*******************************************

bool graph::all(bool perm[]) const
{

      for(int i = 0; i < size; i++)
      {
            if(perm[i] == false)
                  return false;

      }

      return false;

}

*****************************************
"Too much code not necessarily means that something is wrong. Did your prog work?"

no, it crashes somewhere in the first for loop in the big while loop.

"But Dijkstra's algorithm needs to find minimum length for *all* vertices - not isolated - of the graph."
correct, i have these loops in isolation and i believe i was able to fix the first for loop in the while statement, but still haveing problems with the last for in the while loop.

I changed a few things, but it's still crashing somewhere and I just don't know why.

New CODE:
****************************************************

void graph::short_path_graph(int s)
{
      bool * permanent;
      permanent = new bool [size];

      for(int x = 0; x < size; x++)
      {
            permanent[x] = false;
      }


      for(int i = 1; i < size; i++)
      {
            distance[s][i] = INT_MAX;
      }


      permanent[s] = true;
      distance[s][s] = 0;
      int curr = s;

      while(!all(permanent))
      {
            int u = 0;
            int v = 0;

            for(int i = 0; i < size; i++)
            {
                  if(!permanent[i])
                  {
                        int new_dist = adj_matrix[s][curr]+adj_matrix[curr][i];

                        if(new_dist < distance[s][i])
                              distance[s][i] = new_dist;
                  }
            }





            permanent[v] = true;

            int k = 0;

            for(u = 0; u < size; u++)
            {
                  int m = INT_MAX;


                  if(!permanent[u])
                  {
                        if(distance[s][u] < m)
                        {
                              m = distance[s][u];
                              k = u;

                        }

                  }



            curr = k;

            permanent[k] = true;

            precede[s][u] = m;

            }

      }

}