# Shortest Path

Discussion in 'Intelligence & Machines' started by anis, Nov 16, 2001.

Not open for further replies.
1. ### anisRegistered Member

Messages:
1
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

3. ### RickॐValued Senior Member

Messages:
3,336

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.