multi-level floor plan graph mapping

There's a collection of buildings each having multiple floors that are interconnected by stairs and lifts. Currently, I'm attempting to design a system that will find the shortest-path between two points across the any of the buildings, being the same building or in another building.

At the moment each floor is modeled in a graph as follows: the door of each room is a vertex. the junctions of edges connecting the rooms to the main edge(corridor) is also a vertex. The stairs between the floors are edges.

The question that remains is how should I represent the lifts(elevators) (which are right next to the stairs)? To have it as an edge makes me wonder what weight it should have, given that I'll have to run a graph traversal algorithm after for finding the shortest path.

Lift(elevator) as edge or开发者_JAVA技巧 as vertex? That is the question. thanks!

Edges

Using an edge is the most immediate answer, as you do that for stairs. However, while stairs can only go from floor X to floor X+1, a lift can go from any floor to any floor, with slightly different times - I usually find the stairs quicker for two floors, but slower for more than 2. To mirror this you'll need an edge from every floor to every other floor, complete with weightings for each.

Vertices

You could instead have some additional vertices as well as edges. If you had a vertex at each floor of the liftshaft, then you'd only need a single path of edges connecting all the floors together, rather than a combinatorial number of edges.

If you also added an additional vertex outside the doors at each level, then you could add the average delay for getting into a lift and so reflect the fact that a lift can pass multiple floors quickly. However, lifts are going to need average timings at best. At busy times, they can end up stopping at almost every floor anyway, so for a busy campus you wouldn't really gain from these extra vertices.

My vote is for a vertex for each floor of the lift and a single edge to link adjacent floors. It should simplify the graph and reduce the effort of any path-optimisation algorithm as there are fewer paths. Plus it is a more accurate reflection of reality and minimises your workload to set up the edge weights.

If the lifts are a possible shortest path from one floor to the next, then they must be edges with weights. The entrances to each level are vertices. If close enough to the stairs then they are possible shared with the stair vertices.

I vote for edge.

Say you choose to use an elevator. You walk to it, press button and wait a bit. You then get in, wait some more, get out and continue your walk. Now, although you are physically not moving much, in time you are moving. Taking a lift between floors is like walking, say, 50 meters.

What I mean is that the time spent standing around the elevator is equivalent to a distance that you travel if walking. So treat the elevator as an edge that you are walking along during the duration that you are using it. Use that distance to compare, say, walking down the stairs.