Problem Detail: I want to write up a shortest as well as optimal path program for indoor navigation for people with disabilities. For the initial part of the assignment i wish to test my program through graph traversal. My application is supposed to take in a user group then based on that give the appropriate path. The edges are supposed to have 2 values. One for distance and one for quality. I.e distance for path and quality could be set as is it wheelchair accessible or not. Want program to take in graph with 2 values for edge (weight, quality). Remove all paths going through stairs immediately. Regardless of the distance of going through stairs. Then i want program to check the shortest path among the wheelchair accessible path to see if any is available or not. I want a quality value of 1 for accessible and 2 for inaccessible. So if there is a long path going through an elevator with quality 1 then that path should be taken otherwise the shortest path with quality 1 should be displayed. All edges as W are elevators and S are stairs What I want in the code is this. A graph which has 2 things defined on its edge (weight, quality) new Graph.Edge(“b”, “e”, 4,1), Weight could be for the distance but the quality decides the optimal route. I.e. if this is the easiest way to reach there even though it is short. All nodes indicating W indicate elevators. All nodes S are stairs. What I want the code to do is build the map using both defined edges (dist, qual) Then I want all routes going through stairs removed. (The reason they are there is because later on I need this to accommodate abled people too so the program would work in different user groups) Right now I am only bothered with the wheelchair accessibility. This is how the program should go: Remove all stair nodes from being browsed through. Find shortest path to destination going through elevator (W) only Compare that path to the second value quality- new Graph.Edge(“b”, “e”, 4,1), If the quality is = 1 then that is the optimal path to take is ok. If the quality is = 2 then give the longer path instead. If there are 2 paths with the same weight then obviously give the path with quality =1 If both have quality = 1 then just give the one going through least nodes.’ The below code that i have gives a shortest distance using only the distance value and now i am trying to modify that to suit the above criteria but have no idea how to go about it.
import java.util.HashMap; import java.util.Map; import java.util.NavigableSet; import java.util.TreeSet; public class Dijkstra { private static final Graph.Edge[] GRAPH = { new Graph.Edge("a", "b", 2,1), new Graph.Edge("a", "w", 5,1), new Graph.Edge("a", "e", 5,2), new Graph.Edge("a", "d", 7,1), new Graph.Edge("a", "s", 6,1), new Graph.Edge("b", "c", 3,1), new Graph.Edge("b", "e", 4,1), new Graph.Edge("b", "w", 3,2), new Graph.Edge("b", "s", 4,2), new Graph.Edge("b", "d", 6,1), new Graph.Edge("c", "e", 4,1), new Graph.Edge("c", "w", 1,1), new Graph.Edge("w", "c", 1,1), new Graph.Edge("c", "s", 2,2), new Graph.Edge("c", "d", 3,1), new Graph.Edge("d", "w", 2,2), new Graph.Edge("d", "s", 1,1), new Graph.Edge("d", "e", 3,1), new Graph.Edge("e", "w", 4,2), new Graph.Edge("e", "s", 5,1), new Graph.Edge("w", "h", 5,1), new Graph.Edge("h", "w", 5,2), new Graph.Edge("s", "h", 1,1), new Graph.Edge("h", "i", 10,1), new Graph.Edge("i", "h", 10,1), new Graph.Edge("i", "g", 5,1), new Graph.Edge("h", "g", 11,1), new Graph.Edge("h", "j", 12,1), new Graph.Edge("i", "j", 3,1), new Graph.Edge("g", "j", 2,2), }; private static final String START = "d"; private static final String END = "h"; public static void main(String[] args) { Graph g = new Graph(GRAPH); g.dijkstra(START); g.printPath(END); //g.printAllPaths(); } } class Graph { private final Map<String, Vertex> graph; // mapping of vertex names to Vertex objects, built from a set of Edges /** One edge of the graph (only used by Graph constructor) */ public static class Edge { public final String v1, v2; public final int dist; private int qual; public Edge(String v1, String v2, int dist, int qual) { this.v1 = v1; this.v2 = v2; this.dist = dist; this.qual = qual; } } /** One vertex of the graph, complete with mappings to neighbouring vertices */ public static class Vertex implements Comparable<Vertex> { public final String name; public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity private Object qual; public Vertex previous = null; public final Map<Vertex, Integer> neighbours = new HashMap<>(); public Vertex(String name) { this.name = name; } private void printPath() { if (this == this.previous) { System.out.printf("%s", this.name); } else if (this.previous == null) { System.out.printf("%s(unreached)", this.name); } else { this.previous.printPath(); System.out.printf(" -> %s(%d)", this.name, this.dist, this.qual); } } @override public int compareTo(Vertex other) { return Integer.compare(dist, other.dist); } } /** Builds a graph from a set of edges */ public Graph(Edge[] edges) { graph = new HashMap<>(edges.length); //one pass to find all vertices for (Edge e : edges) { if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); } //another pass to set neighbouring vertices for (Edge e : edges) { graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist); // graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph } } /** Runs dijkstra using a specified source vertex */ public void dijkstra(String startName) { if (!graph.containsKey(startName)) { System.err.printf("Graph doesn't contain start vertex "%s"n", startName); return; } final Vertex source = graph.get(startName); NavigableSet<Vertex> q = new TreeSet<>(); // set-up vertices for (Vertex v : graph.values()) { v.previous = v == source ? source : null; v.dist = v == source ? 0 : Integer.MAX_VALUE; q.add(v); } dijkstra(q); } /** Implementation of dijkstra's algorithm using a binary heap. */ private void dijkstra(final NavigableSet<Vertex> q) { Vertex u, v; while (!q.isEmpty()) { u = q.pollFirst(); // vertex with shortest distance (first iteration will return source) if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable //look at distances to each neighbour for (Map.Entry<Vertex, Integer> a : u.neighbours.entrySet()) { v = a.getKey(); //the neighbour in this iteration final int alternateDist = u.dist + a.getValue(); if (alternateDist < v.dist ) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn't contain end vertex "%s"n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v : graph.values()) { v.printPath(); System.out.println(); } }
}
Asked By : Jason6916
Answered By : babou
What you may want is the use a “metric” on a pair of values, such that one value always has precedence over the other. In this way, you actually consider any length of stairs to be worse than any path without stairs, but you can discriminate also on the length of stairways. The way you do this is to mesure a distance as a pair $[w,c]$, where $w$ stands for walk and $c$ stands for climb. The value $w$ can be a distance in meters, and the value of $c$ can be the number of steps to climb, or any other measure of inaccessibility. This is the same as weight and quality suggested by the question, but it seems a terminology closer to the problem at hand. Then you define:
- $[w,c] < [w’,c’];;$ iff $;;c<c’ ;vee; (c=c’ wedge w<w’)$, which is just lexicographic order on pairs of values.
- $[w,c] + [w’,c’] = [ w+w’, c+c’]$
Then you can just use the pairs as measure of distance in Dijkstra’s algorithm, to get the most convenient path. If you do not want to distinguish degrees of inaccessibility, you can take the value of $c$ in the set ${0,1}$, with $1+1=1$ for the $c$ component of the pair, which is the same as using a boolean value. There are other variations, depending on what you want to take into account, and how. For example, you might consider that all stairs are equivalent, independently of the number of steps. Or that some stairs are more difficult for the same number of steps. There is a coding trick that you can also use, if you know that you will never exceed a given walking distance $D$ on any path that you ever follow. Then you can encode $w,c$ as $w+cD$ and use that as distance. But the computational gain is probably not worth it, and it could lead you to bugging your algorithm as it evolves.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/43083 Ask a Question Download Related Notes/Documents
