Shortest Path

HI...
I want some guidance.. I am developing an information Kiosk as my final year project in B.Sc Computing. It is a intelligent information Kiosk, which show users also a 3D walk thorough to any location inside a building. In an Architecture(Building), How i can find the shortest path?.. Can u give me some idea.. Tell me some algorithm that i can implement.. I have all vlaues of the Architecture, i mean size of Rooms, Cooridors etc... What Algorithm and search technique i can use?

Thanks
Anis

Please Register or Log in to view the hidden image!

 

Log in or Sign up to hide all adverts.

PLEASE CONSULT KREYZIG'S ADVANCED MATHEMATICS PG NO 1015

hi,
this may be of some help,its called exactly moores BFS algorithm.

the algorithm determines a shortest path in a connected graph
G=(V,E) from a vertex t.

INPUT:connected graph G = (V,E),in which one vertex is denoted by s and one by t,and each edge (i,j) has length Lij=1.initially all vertices are unlabeled.

OUTPUT: a shortest path s->t in G=(V,E).

1.)label s with 0.
2.)set i=0.
3.)find unlabelded vertices adjacent to a vertex labelled i.
4.)label the vertices found with i+1.
5.)if vertex t is labelled,then backtracking gives shortest path

k(=label of t),k,k-1,k-2,...,0.

OUTPUT k,k-1,k-2...,0,STOP.

else increase i by 1.

goto step 3.

END MOORE.

 

Log in or Sign up to hide all adverts.