Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

[c++]assignment help - dijkstra algorithm based on adjacent matrix.

pseudocode shortest path matrix

  • Please log in to reply
5 replies to this topic

#1 notes

notes

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 88 posts
  • Location:Poland
  • Programming Language:C++
  • Learning:Java, C#

Posted 13 September 2011 - 03:31 PM

Hi,
I really could use some help with my asigment.
As it is in the title, I have to write program, based on non weighted and undirected graph, which will find shortest path between two locations. There are like 25 locations and I figured out that the fastest way to declare them is by adjacent matrix. It would be hard to define ~100 branch or lists for 25 vertexes.
I've started with small numbers just to figure out algorithm first and i have major problem.

Here is how declared graph looks like :
graph.jpg

Im trying to figure it out by myself, but I've read some codes and pseudocodes, If any of them is based on matrix is directed :(

Here is my code :
#include <cstdlib>
#include <iostream>
const int n =7;
int number[7]= {1,2,3,4,5,6,7};
char *name[7]={"One","Two","Three","Four","Five","Six","Seven"};
using namespace std;

struct graph {
   int L[n][n];
   int numbersVisited[30]; // for saving numbers(names) of visited vertex
   int tempNumber[30];
   int visited;

   graph ();
   void MatrixShow();
   void find(int start, int dest);
   void search(int max, int dest, int temp);
};


graph :: graph ()
{
    
    for (int i=0;i<n;i++) // inserting '0'
    {
        for (int j=0;j<n;j++)
         L[i][j]=0;   
    }
// Inserting connections
    L[0][2]=1;
    L[0][4]=1;
    L[1][3]=1;
    L[1][4]=1;
    L[2][3]=1;
    L[2][4]=1;
    L[3][5]=1;
    L[5][6]=1;
// Graph is undirected so matrix is symetric -> Matrix[m][n]=Matrix[n][m];
    for (int i=0;i<n;i++) 
    {
         for (int j=0;j<n;j++)
         {
             if(L[i][j])
                 L[j][i]=L[i][j];
         } 
    } 
}

void graph::MatrixShow()
{
    cout <<"Graph nxn : \n";
    for (int i=0;i<=n;i++)
    {
        cout << (i)<< " ";
        
        for (int j=0;j<n;j++)
        {
            if (i==0)
            { 
                for (int k=1; k<=n;k++)
                    { cout << k << " "; }
                j=n; 
            }
            if (i)     
                {cout << L[(i-1)][j] << " "; }
        }
        cout <<endl;
    }


}

void graph::search (int max, int dest,int temp)
{
 
 if(max>visited)
 {
   if (L[temp][dest])
   {
      cout << "Connection found\n";
      visited++;
      tempNumber[visited]=temp;
      
      

   }
   if (!L[temp][dest])
   {
      visited++;
      tempNumber[visited]=temp;
      for (int i=0;i<n;i++)
      {
         if (L[i][temp])
            search(max,dest,i);
      }
      
   
   }
  }
  
}


void graph::find(int start, int dest)
{
    start-=1;
    dest-=1;
    if(L[start][dest]==1)
    {
        cout <<"Station "<< name[start]<<" and " << name[dest]
             << " is directly connected.\n";
    }
    if (!L[start][dest])
    {
        int max=8;
        visited=0;
       
        int temp=start;
        tempNumber[0]=number[start];
        
        for (int i=0;i<n;i++)
        {
            cout << i;
            if (L[start][i])
            {
                visited=0;
                
                search(max,dest,i);
                
                if (visited<max)
                {
                max = visited;
                for (int j=0; j<max;j++)
                  {   numbersVisited[j]=tempNumber[j]; }
                }
            }
        }
    }
}

int main(int argc, char *argv[])
{
    graph G;
    G.MatrixShow();
    int a,b;
    cout << "\nStart and destination " ;
    cin >> a >> b;
    cout << endl;
    G.find(a,b);
    system("PAUSE");
    return EXIT_SUCCESS;
}

  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 14 September 2011 - 04:35 AM

You can convert your undirected graph into a directed graph by simply creating a second edge for each existing edge, and declaring them to be in opposite directions.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 notes

notes

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 88 posts
  • Location:Poland
  • Programming Language:C++
  • Learning:Java, C#

Posted 15 September 2011 - 03:09 AM

Just like I did :

// Inserting connections
    L[0][2]=1;
    L[0][4]=1;
    L[1][3]=1;
    L[1][4]=1;
    L[2][3]=1;
    L[2][4]=1;
    L[3][5]=1;
    L[5][6]=1;
// Graph is undirected so matrix is symetric -> Matrix[m][n]=Matrix[n][m];
    for (int i=0;i<n;i++) 
    {
         for (int j=0;j<n;j++)
         {
             if(L[i][j])
                 L[j][i]=L[i][j];
         } 
    } 

Im stuck with the algorithm, Ive figured out the way how to declare nodes with adjacent list for each of node based on my matrix but, basicly im stuck in the same point - making my algorithm work properly. Now I even dont know if it should be dijkstra or just BFS(if so, how to store a path?) ;/
  • 0

#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 15 September 2011 - 04:44 AM

BFS using nodes as a structure that has a list of "neighbors" was my idea.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#5 notes

notes

    CC Resident

  • Advanced Member
  • PipPipPipPip
  • 88 posts
  • Location:Poland
  • Programming Language:C++
  • Learning:Java, C#

Posted 15 September 2011 - 05:08 PM

Ok, done. If any-one needed code pm me.
BFS was much more easier, thanks for the tip.
  • 0

#6 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 15 September 2011 - 06:54 PM

The great thing about programming is there's usually more than one approach. An interesting question, if you get both approaches working, would be "which scales better?"
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/






Also tagged with one or more of these keywords: pseudocode, shortest path, matrix

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download