Re: Graphs: Arbitrary Dijkstra's algorithm implementation

[b klein <b_klein1@yahoo.com>]

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