* Graphs: Arbitrary Dijkstra's algorithm implementation
@ 2003-12-16 15:06 Fabio Miranda Hamburger
2003-12-16 20:46 ` b klein
0 siblings, 1 reply; 4+ messages in thread
From: Fabio Miranda Hamburger @ 2003-12-16 15:06 UTC (permalink / raw)
To: linux-c-programming
[-- 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();
}
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: Graphs: Arbitrary Dijkstra's algorithm implementation
2003-12-16 15:06 Graphs: Arbitrary Dijkstra's algorithm implementation Fabio Miranda Hamburger
@ 2003-12-16 20:46 ` b klein
2003-12-17 3:53 ` Glynn Clements
0 siblings, 1 reply; 4+ messages in thread
From: b klein @ 2003-12-16 20:46 UTC (permalink / raw)
To: Fabio Miranda Hamburger; +Cc: linux-c-programming
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
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: Graphs: Arbitrary Dijkstra's algorithm implementation
2003-12-16 20:46 ` b klein
@ 2003-12-17 3:53 ` Glynn Clements
2003-12-17 18:04 ` Fabio Miranda Hamburger
0 siblings, 1 reply; 4+ messages in thread
From: Glynn Clements @ 2003-12-17 3:53 UTC (permalink / raw)
To: b klein; +Cc: Fabio Miranda Hamburger, linux-c-programming
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>
^ permalink raw reply [flat|nested] 4+ messages in thread* Re: Graphs: Arbitrary Dijkstra's algorithm implementation
2003-12-17 3:53 ` Glynn Clements
@ 2003-12-17 18:04 ` Fabio Miranda Hamburger
0 siblings, 0 replies; 4+ messages in thread
From: Fabio Miranda Hamburger @ 2003-12-17 18:04 UTC (permalink / raw)
To: Glynn Clements; +Cc: b klein, linux-c-programming
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.
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2003-12-17 18:04 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2003-12-16 15:06 Graphs: Arbitrary Dijkstra's algorithm implementation Fabio Miranda Hamburger
2003-12-16 20:46 ` b klein
2003-12-17 3:53 ` Glynn Clements
2003-12-17 18:04 ` Fabio Miranda Hamburger
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).