P
Piotre Ugrumov
Excuse me if I'm repetitive but I need help.
I thank Micheal Dunn but his suggestion is too particular and it's too
legates to a specific map of a museum.
I have this problem.
I have a map of a generic museum. Every room has maximum 4 links to other
room. These links have not a cost(the cost is always 1). I must implement a
algorithm to determinate the shortest path from a room to another room.
I have created a Class room, this class have these methods eand these data:
Method:
public int getNumVicini() //this method gives the number of room linked the
the object room in question;
public int getVicino(int v)//this method returns the 1st or the2nd or the
3rd or the 4th
public int getId()//return the id of the room
public String getPercorsi(int i)//return the path from the object room to
the room with id equals to i
public boolean verifyVicino(int v)//This method verify if a room with id
equals to v is linked to the object room
The there are the method addVicino(int i) that insert i inthe array vicini,
the method setname, setid, getname, getid etc.
Data:
private int vicini[]=new int[4];//this array contains the id of the linked
rooms
public String percorsi[]= new String[9];//this array contain the path from
the object room to all the others rooms in percorsi[0] there is the path
from object room to the room with id=0, in percrosi[1] path from object room
to the room with id[1], etc.
private int id;//in this int there's the id of the room
private String nome;//in this string there's the name of the room
In the main I have an array that contains all the room of the museum(Room
museum[]=new Room[x]).
The I have created a class Path to determinate the shortest path from a room
to another room.
This is the class Path:
public class Path {
private Room start;
public Path(Room r){ //the constructor take a room the room of start
and set the path to the linked room
for(int i=0; i<r.getNumVicini(); i++){
r.verifica[r.getVicino(i)]=true; //r.getVicino(i) give the id of
the linked rooms and set the verify[x], where x is the id of the linked
room, to true, because the shortest path is immediate
r.percorsi[r.getVicino(i)]+=r.getId()+ " " +
r.getVicino(i);//set the path to the linked room i equals to the id of the
start room an the id of the end room in this case the is of the end room is
the id a linked room
}
start=r;//it assigns the object r to start
}
private void findRoad2(Room end){ //this method permit to calculate
the path from 2 rooms that have a common linked room, but I don't know how
do to determinate a path for 2 room if between these 2 rooms there is more
of one room for example if I have these room 2-9-6-8(hte number are the id
of the room , the - are the link), with this method I am able to
derterminate the path from 2 to 9, from 2 to 6, but not for 2 to 8
for(int i=0; i<start.getNumVicini(); i++){
for(int j=0; j<end.getNumVicini(); j++){
if(start.getVicino(i)==end.getVicino(j) &&
start.verifica[end.getId()]==false){//This cycle verify if there is a common
linked room(like the room 9 in the example of the path from 2to6)
start.verifica[end.getId()]=true; //if there is this
common linked room it sets the verify[end.getId()] to true to indicate that
the path it is been determinated
start.percorsi[end.getId()]=start.getId()+ " " +
start.getVicino(i) + " " + end.getId(); //set the path, this path is equals
to start id and the id of the common linked room and end room id
}
}
}
}
If I have a map of the museum of this type:
7-8-3
| | |
6-4-2
| | |
5-0-1
(this map is only an example I could have a museum with 13 rooms that are
arranged in irregular way)
with the code that I have written I can determinate the path from 7 to 8,
from 7 to 6, from 7 to 4, from 7 to 3 and from 7 to 5, but NOT from 7 to 0,
from 7 to 1 or from 7 to 2
At the same way I can determinate the path from 0 to 5, from 0 to 1m from 0
to 4, from 0 to 8, from 0 to 2, from 0 to 6, but NOT from 0 to 3, from 0 to
7.
The some thing is for the rest of the rooms. I don't know how do to
determinate the rest of the path.
How can I do?
Thanks and excuse me.
I thank Micheal Dunn but his suggestion is too particular and it's too
legates to a specific map of a museum.
I have this problem.
I have a map of a generic museum. Every room has maximum 4 links to other
room. These links have not a cost(the cost is always 1). I must implement a
algorithm to determinate the shortest path from a room to another room.
I have created a Class room, this class have these methods eand these data:
Method:
public int getNumVicini() //this method gives the number of room linked the
the object room in question;
public int getVicino(int v)//this method returns the 1st or the2nd or the
3rd or the 4th
public int getId()//return the id of the room
public String getPercorsi(int i)//return the path from the object room to
the room with id equals to i
public boolean verifyVicino(int v)//This method verify if a room with id
equals to v is linked to the object room
The there are the method addVicino(int i) that insert i inthe array vicini,
the method setname, setid, getname, getid etc.
Data:
private int vicini[]=new int[4];//this array contains the id of the linked
rooms
public String percorsi[]= new String[9];//this array contain the path from
the object room to all the others rooms in percorsi[0] there is the path
from object room to the room with id=0, in percrosi[1] path from object room
to the room with id[1], etc.
private int id;//in this int there's the id of the room
private String nome;//in this string there's the name of the room
In the main I have an array that contains all the room of the museum(Room
museum[]=new Room[x]).
The I have created a class Path to determinate the shortest path from a room
to another room.
This is the class Path:
public class Path {
private Room start;
public Path(Room r){ //the constructor take a room the room of start
and set the path to the linked room
for(int i=0; i<r.getNumVicini(); i++){
r.verifica[r.getVicino(i)]=true; //r.getVicino(i) give the id of
the linked rooms and set the verify[x], where x is the id of the linked
room, to true, because the shortest path is immediate
r.percorsi[r.getVicino(i)]+=r.getId()+ " " +
r.getVicino(i);//set the path to the linked room i equals to the id of the
start room an the id of the end room in this case the is of the end room is
the id a linked room
}
start=r;//it assigns the object r to start
}
private void findRoad2(Room end){ //this method permit to calculate
the path from 2 rooms that have a common linked room, but I don't know how
do to determinate a path for 2 room if between these 2 rooms there is more
of one room for example if I have these room 2-9-6-8(hte number are the id
of the room , the - are the link), with this method I am able to
derterminate the path from 2 to 9, from 2 to 6, but not for 2 to 8
for(int i=0; i<start.getNumVicini(); i++){
for(int j=0; j<end.getNumVicini(); j++){
if(start.getVicino(i)==end.getVicino(j) &&
start.verifica[end.getId()]==false){//This cycle verify if there is a common
linked room(like the room 9 in the example of the path from 2to6)
start.verifica[end.getId()]=true; //if there is this
common linked room it sets the verify[end.getId()] to true to indicate that
the path it is been determinated
start.percorsi[end.getId()]=start.getId()+ " " +
start.getVicino(i) + " " + end.getId(); //set the path, this path is equals
to start id and the id of the common linked room and end room id
}
}
}
}
If I have a map of the museum of this type:
7-8-3
| | |
6-4-2
| | |
5-0-1
(this map is only an example I could have a museum with 13 rooms that are
arranged in irregular way)
with the code that I have written I can determinate the path from 7 to 8,
from 7 to 6, from 7 to 4, from 7 to 3 and from 7 to 5, but NOT from 7 to 0,
from 7 to 1 or from 7 to 2
At the same way I can determinate the path from 0 to 5, from 0 to 1m from 0
to 4, from 0 to 8, from 0 to 2, from 0 to 6, but NOT from 0 to 3, from 0 to
7.
The some thing is for the rest of the rooms. I don't know how do to
determinate the rest of the path.
How can I do?
Thanks and excuse me.