Graphs: Arbitrary Dijkstra's algorithm implementation

Graphs: Arbitrary Dijkstra's algorithm implementation

[Fabio Miranda Hamburger]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1209 bytes --]

Hi.

I am trying to code a small program in Ansi C++ that somehow implements
the famous Dijkstra algorithm that looks for the shortest path between 2
nodes in a dinamic bidirectional directed pointer graph.

Attached You will find the .cpp with both clases and implementations.
The algorithm looks for the shortest path between 1 and a given node,
actually, the algorithm follow common graph implementation and uses a
static biarray of "weights" (a distance between x -> y), for example,
weight[2][5] = 10 means that there is a cost of 10 from 2 to 5 without a
scale in a other node of the same type.

However, the algorithm is unable to use n > 6 nodes and I dont understand
why, after a depuration and reading Tenenbaum's, I found out a function
return "infinity" and afterwards an address memory violation. The
algorithm should never return infinite because there is always a pending
distance of the (latest-1 node ) != infinite

I would really appreciate any comments or help, my goal is to code a
algorithm that takes a matrix of weigth and prints out the nodes of the
shortest path of (1,x)

best regards,


---
Fabio Andres Miranda
Ingenieria de sistemas informaticos
Universidad Latina - Costa Rica



[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: TEXT/x-c++src; name="dijsktra.cpp", Size: 3855 bytes --]

#define     NODES   8
#define     INFINITY    10000 //the value representing a not numerical result path
#define     costos  weight  // spanish -> english

// problem =>  if nodes <= 8 the algorithm doesnt work

#include<iostream.h>
#include<conio.h>
#include<string.h>

class grafo // es la clase donde esta la clase y los algoritmos
{
  public:
  void dijkstra(void);
  void mascorto(void);
  void caminos(int i, int j);
  grafo(void) //inicializa la matriz de costos y los vectores temporales
  {
      for (int i=1; i<=7; i++)
	 for (int j=1; j<=7; j++)
	  costos[i][j]=10000;
      costos[1][2]=200;
      costos[1][4]=150;
      costos[2][3]=100;
      costos[3][1]=50;
      costos[3][7]=25;
      costos[4][3]=500;
      costos[4][5]=200;
      costos[5][6]=175;
      costos[6][3]=250;
      costos[7][5]=300;
      for (int i=1; i<=7; i++)
      {
	 vertices[i]=i;
	 vertices2[i]=i;
      }
  }
  int D[NODES];//aqui van quedando los costos minimos
  private:
     int vertices[NODES]; //se guardan los vertices
     int p[NODES][NODES];//se utiliza para sacar los caminos
     int costos[NODES][NODES];//matriz donde estan los costos de ir de un vertice a otro
     int vertices2[NODES];//aqui van quedando los vertices visitados
     int w;//contiene el vertice visitado actualmente
     int buscaminimo(void);
     int min(int x, int y);
};
void grafo::dijkstra(void) //calcula los caminos minimos desde el vertice 1 hacia los demas
{
    int conjunto[NODES]; // aqui se van guardando los vertices no visitados
    int posconjunto=1;
    vertices[posconjunto]=0;
    D[1]=0;
    for (int i=2; i<=NODES-1; i++)
	D[i]=costos[1][i]; //inicializa el vector con los costos de 1 a i
    for(int i=1; i<= NODES-2; i++)
    {
      w=buscaminimo();//deja en w el vertice no visitado con el menor costo en ese momento
      posconjunto++;
      conjunto[posconjunto]=w;//inserta al vertice en los visitados
      vertices2[w]=0;//saca al vertice los no visitados
      for (int v=NODES-1-posconjunto; v<=7; v++)
	 D[v]=min(D[v],D[w]+costos[w][v]);//analiza si es menor por este camino(w) o por el que esta en este momento
    }
};
int grafo::buscaminimo(void)//busca el vertice con costo minimo de los no visitados
{
	int minimo=10000, pos=10000;
	for(int i=1; i<=NODES-1; i++)
	{
	  if (vertices2[i] !=0)
	     if (D[i] < minimo)
	     {
		minimo=D[i];
		pos=i;
	     }
	}
	return pos;
};
int grafo::min(int x, int y)//retorna el valor con menor costo
{
  if (x < y)
     return x;
  else
      return y;
};
void grafo::mascorto(void)//saca la ruta de caminos mas cortos entre los vertices
{
  int i,j,k;
  int a[NODES][NODES];
  for (i=1;i<=NODES-1;i++)
    for (j=1;j<=NODES-1;j++)
    {
	a[i][j]=costos[i][j];
	p[i][j]=0;
    }
  for (i=1;i<=NODES-1;i++)
      a[i][i]=0;
  for (k=1;k<=NODES-1;k++)
      for (i=1;i<=NODES-1;i++)
	  for (j=1;j<=NODES-1;j++)
	      if ((a[i][k]+a[k][j])<(a[i][j]))
	      {
		a[i][j]=a[i][k]+a[k][j];
		p[i][j]=k;
	      }
};
void grafo::caminos(int i, int j)//imprime la ruta mas corta desde el vertice i hasta el j
{
   int k;
   char c=' ';
   k=p[i][j];
   if (k==0)
      return;
   caminos(i,k);
   cout<<k;
   cout<<c;
   caminos(k,j);
}
void main (void)
{
 grafo g;
 g.dijkstra();
 g.mascorto();
 char c=' ';
 char s[20]="Camino M¡nimo: ";
 char s2[20]="Costo: ";
 for (int i=1; i<=NODES-1; i++)//este ciclo imprime los caminos minimos desde el vertice 1 hasta los dem s
 {
   cout << s;
   cout << 1;
   cout << c;
   g.caminos(1,i);
   cout << i;
   cout << c;
   cout << s2;
   cout << g.D[i]<<"\n";
 }
   getch();
}

Re: Graphs: Arbitrary Dijkstra's algorithm implementation

[b klein]

hi
im a beginner here so please say if i do something off
topic.
i tried to set 
#define     NODES   8
and then(i hope this is right) i changed the
constructor:
grafo(void) //inicializa la matriz de costos y los
> vectores temporales
>   {
>       //for (int i=1; i<=7; i++) was
> 	 //for (int j=1; j<=7; j++)
now 
       for (int i=1; i<=NODES; i++) was
 	for (int j=1; j<=NODES; j++)
 	  costos[i][j]=10000;

>       costos[1][2]=200;
>       costos[1][4]=150;
>       costos[2][3]=100;
>       costos[3][1]=50;
>       costos[3][7]=25;
>       costos[4][3]=500;
>       costos[4][5]=200;
>       costos[5][6]=175;
>       costos[6][3]=250;
>       costos[7][5]=300;
>      // for (int i=1; i<=7; i++)
        for (int i=1; i<=NODES; i++)
>       {
> 	 vertices[i]=i;
> 	 vertices2[i]=i;
>       }
and then i founf´d that in the method 
int grafo::buscaminimo(void)//busca el vertice con
// costo minimo de los no visitados
 {
 	int minimo=10000, pos=10000;
pos doesnt change, but it is returned. and the value
is used as an index of vertices2[w] in the method 
dijkstra(void).
vertices2[] has a size of NODES.
so the index w=10000 is out of size.

--- Fabio Miranda Hamburger
<fabmirha@ns.isi.ulatina.ac.cr> wrote:
> Hi.
> 
> I am trying to code a small program in Ansi C++ that
> somehow implements
> the famous Dijkstra algorithm that looks for the
> shortest path between 2
> nodes in a dinamic bidirectional directed pointer
> graph.
> 
> Attached You will find the .cpp with both clases and
> implementations.
> The algorithm looks for the shortest path between 1
> and a given node,
> actually, the algorithm follow common graph
> implementation and uses a
> static biarray of "weights" (a distance between x ->
> y), for example,
> weight[2][5] = 10 means that there is a cost of 10
> from 2 to 5 without a
> scale in a other node of the same type.
> 
> However, the algorithm is unable to use n > 6 nodes
> and I dont understand
> why, after a depuration and reading Tenenbaum's, I
> found out a function
> return "infinity" and afterwards an address memory
> violation. The
> algorithm should never return infinite because there
> is always a pending
> distance of the (latest-1 node ) != infinite
> 
> I would really appreciate any comments or help, my
> goal is to code a
> algorithm that takes a matrix of weigth and prints
> out the nodes of the
> shortest path of (1,x)
> 
> best regards,
> 
> 
> ---
> Fabio Andres Miranda
> Ingenieria de sistemas informaticos
> Universidad Latina - Costa Rica
> 
> 
> > #define     NODES   8
> #define     INFINITY    10000 //the value
> representing a not numerical result path
> #define     costos  weight  // spanish -> english
> 
> // problem =>  if nodes <= 8 the algorithm doesnt
> work
> 
> #include<iostream.h>
> #include<conio.h>
> #include<string.h>
> 
> class grafo // es la clase donde esta la clase y los
> algoritmos
> {
>   public:
>   void dijkstra(void);
>   void mascorto(void);
>   void caminos(int i, int j);
>   grafo(void) //inicializa la matriz de costos y los
> vectores temporales
>   {
>       for (int i=1; i<=7; i++)
> 	 for (int j=1; j<=7; j++)
> 	  costos[i][j]=10000;
>       costos[1][2]=200;
>       costos[1][4]=150;
>       costos[2][3]=100;
>       costos[3][1]=50;
>       costos[3][7]=25;
>       costos[4][3]=500;
>       costos[4][5]=200;
>       costos[5][6]=175;
>       costos[6][3]=250;
>       costos[7][5]=300;
>       for (int i=1; i<=7; i++)
>       {
> 	 vertices[i]=i;
> 	 vertices2[i]=i;
>       }
>   }
>   int D[NODES];//aqui van quedando los costos
> minimos
>   private:
>      int vertices[NODES]; //se guardan los vertices
>      int p[NODES][NODES];//se utiliza para sacar los
> caminos
>      int costos[NODES][NODES];//matriz donde estan
> los costos de ir de un vertice a otro
>      int vertices2[NODES];//aqui van quedando los
> vertices visitados
>      int w;//contiene el vertice visitado
> actualmente
>      int buscaminimo(void);
>      int min(int x, int y);
> };
> void grafo::dijkstra(void) //calcula los caminos
> minimos desde el vertice 1 hacia los demas
> {
>     int conjunto[NODES]; // aqui se van guardando
> los vertices no visitados
>     int posconjunto=1;
>     vertices[posconjunto]=0;
>     D[1]=0;
>     for (int i=2; i<=NODES-1; i++)
> 	D[i]=costos[1][i]; //inicializa el vector con los
> costos de 1 a i
>     for(int i=1; i<= NODES-2; i++)
>     {
>       w=buscaminimo();//deja en w el vertice no
> visitado con el menor costo en ese momento
>       posconjunto++;
>       conjunto[posconjunto]=w;//inserta al vertice
> en los visitados
>       vertices2[w]=0;//saca al vertice los no
> visitados
>       for (int v=NODES-1-posconjunto; v<=7; v++)
> 	 D[v]=min(D[v],D[w]+costos[w][v]);//analiza si es
> menor por este camino(w) o por el que esta en este
> momento
>     }
> };
> int grafo::buscaminimo(void)//busca el vertice con
> costo minimo de los no visitados
> {
> 	int minimo=10000, pos=10000;
> 	for(int i=1; i<=NODES-1; i++)
> 	{
> 	  if (vertices2[i] !=0)
> 	     if (D[i] < minimo)
> 	     {
> 		minimo=D[i];
> 		pos=i;
> 	     }
> 	}
> 	return pos;
> };
> int grafo::min(int x, int y)//retorna el valor con
> menor costo
> {
>   if (x < y)
>      return x;
>   else
>       return y;
> };
> void grafo::mascorto(void)//saca la ruta de caminos
> mas cortos entre los vertices
> {
>   int i,j,k;
>   int a[NODES][NODES];
>   for (i=1;i<=NODES-1;i++)
>     for (j=1;j<=NODES-1;j++)
>     {
> 	a[i][j]=costos[i][j];
> 	p[i][j]=0;
>     }
>   for (i=1;i<=NODES-1;i++)
>       a[i][i]=0;
>   for (k=1;k<=NODES-1;k++)
>       for (i=1;i<=NODES-1;i++)
> 	  for (j=1;j<=NODES-1;j++)
> 	      if ((a[i][k]+a[k][j])<(a[i][j]))
> 	      {
> 		a[i][j]=a[i][k]+a[k][j];
> 		p[i][j]=k;
> 	      }
> };
> void grafo::caminos(int i, int j)//imprime la ruta
> mas corta desde el vertice i hasta el j
> {
>    int k;
>    char c=' ';
>    k=p[i][j];
>    if (k==0)
>       return;
>    caminos(i,k);
>    cout<<k;
>    cout<<c;
>    caminos(k,j);
> }
> void main (void)
> {
>  grafo g;
>  g.dijkstra();
>  g.mascorto();
>  char c=' ';
>  char s[20]="Camino M¡nimo: ";
>  char s2[20]="Costo: ";
>  for (int i=1; i<=NODES-1; i++)//este ciclo imprime
> los caminos minimos desde el vertice 1 hasta los
> dem s
>  {
>    cout << s;
>    cout << 1;
>    cout << c;
>    g.caminos(1,i);
>    cout << i;
>    cout << c;
>    cout << s2;
>    cout << g.D[i]<<"\n";
>  }
>    getch();
> }
> 
> 
> 


__________________________________
Do you Yahoo!?
New Yahoo! Photos - easier uploading and sharing.
http://photos.yahoo.com/
-
To unsubscribe from this list: send the line "unsubscribe linux-c-programming" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: Graphs: Arbitrary Dijkstra's algorithm implementation

[Glynn Clements]

b klein wrote:

> im a beginner here so please say if i do something off
> topic.
> i tried to set 
> #define     NODES   8
> and then(i hope this is right) i changed the
> constructor:
> grafo(void) //inicializa la matriz de costos y los
> > vectores temporales
> >   {
> >       //for (int i=1; i<=7; i++) was
> > 	 //for (int j=1; j<=7; j++)
> now 
>        for (int i=1; i<=NODES; i++) was
>  	for (int j=1; j<=NODES; j++)
>  	  costos[i][j]=10000;

If costos has dimensions costos[NODES][NODES], the above is invalid;
when i == NODES or j == NODES, you are exceeding the bounds of the
array. If an array has size N, the valid indices range from 0 to N-1
inclusive; N isn't a valid index.

-- 
Glynn Clements <glynn.clements@virgin.net>

Re: Graphs: Arbitrary Dijkstra's algorithm implementation

[Fabio Miranda Hamburger]

HI Glynn.

I thought You were out of linux-c-programming.

> > im a beginner here so please say if i do something off
> > topic.
> > i tried to set
> > #define     NODES   8
> > and then(i hope this is right) i changed the
> > constructor:
> > grafo(void) //inicializa la matriz de costos y los
> > > vectores temporales
> > >   {
> > >       //for (int i=1; i<=7; i++) was
> > > 	 //for (int j=1; j<=7; j++)
> > now
> >        for (int i=1; i<=NODES; i++) was
> >  	for (int j=1; j<=NODES; j++)
> >  	  costos[i][j]=10000;

> If costos has dimensions costos[NODES][NODES], the above is invalid;
> when i == NODES or j == NODES, you are exceeding the bounds of the
> array. If an array has size N, the valid indices range from 0 to N-1
> inclusive; N isn't a valid index

Fixed.
Still not working.