0
$\begingroup$

How to modify Dijkstra's algorithm, for wheel chair users, to take into account the road quality?

There are three levels of quality: $1$ for pure concrete, $2$ for partly concrete and $3$ for rough road.
Taking this into account, if there are roads $p1$: the short distance with road quality $3$ and $p2$: the long distance with quality $1$, the longer path $p2$ is chosen due to easier road difficulty.

The quality of the road is more important than the distance. If there are roads of equal quality the shorter one is chosen.

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Hint: Think of Dijkstra's algorithm not as an algorithm for finding short paths, think of it as an algorithm for finding desirable paths. The only requirement is is that the desirability of an edge is not negative. $\endgroup$
    – adrianN
    Commented Dec 15, 2016 at 8:59
  • $\begingroup$ See also suggestion received at SO: stackoverflow.com/q/41157324/781723 $\endgroup$
    – D.W. ♦
    Commented Dec 15, 2016 at 18:25
  • 1
    $\begingroup$ @adrianN Well, and desirability has to be additive... $\endgroup$
    – Raphael
    Commented Dec 15, 2016 at 19:18
  • $\begingroup$ It's hard to understand what you are asking. Please clarify, take more care with the language, and formulate a better title. Yours could label any number of questions... $\endgroup$
    – Raphael
    Commented Dec 15, 2016 at 19:18
  • 1
    $\begingroup$ Are you suggesting that the algorithm should favor a long road on nice concrete over a short road on rough roads, no matter how long the long road actually is? Or are you saying that the algorithm should treat a rough road as equal to a long road of, say 3x the distance, effectively penalizing the rough roads $\endgroup$
    – Cort Ammon
    Commented Dec 15, 2016 at 22:34

3 Answers 3

Reset to default
3
$\begingroup$

You seem to have chosen a strange metric, in that your wheelchair user apparently prefers travelling 1000km over concrete to even 1cm over gravel.

However, in general, the way to proceed is to combine your two metrics into a single metric in such a way that even the best possible score on the secondary metric can't make the algorithm prefer a path that does worse on the primary metric.

So, I'm going to assume that each edge $e$ has a quality $q_e$ and a length $\ell_e$. The quality will be a nonnegative integer; the length can be a nonnegative real (or integer – it doesn't matter). Because Dijkstra likes to minimize, I'll take $q=0$ to be the best possible quality (in the question, you take it to be the worst, but this makes no real difference).

Any path between two vertices can't possibly have length more than $L = \sum_{e\in E} \ell_e$. This means that, for any path of total length $\ell$, $\ell/(L+1)<1$. We'll take the weight of the edge $e$ to be $w_e = q_e + \ell_e/(L+1)$, and use these values $w_e$ to run Disjkstra's algorithm. The point is that if a path has total quality $Q$, then it has total weight $W$ with $Q\leq W<Q+1$. Therefore, the least-weight path is guaranteed to be one of the best quality paths (smallest $q$-values) and, among those, it's the one of least total length.

Improve this answer
$\endgroup$
1
$\begingroup$

Well each edge could contain a pair of natural numbers. While constructing the shortest path you could consider the road quality first, then the distance if there are potential paths with the same road quality. I hope this helps people with wheelchairs navigate more easily!

Improve this answer
$\endgroup$
4
  • $\begingroup$ actually im a wheelchair user and the title of my research is optimal path for wheelchair user.. my porblem is how to modify the dijkstras algorithm.. i already have the dijktras code but my problem is how to modify it that the quality of the road will be prioritize. $\endgroup$
    – Skywalker
    Commented Dec 15, 2016 at 11:57
  • $\begingroup$ I believe my answer is what you're after. In Dijkstra's when you search for the vertex with min weight from the current vertex you can take note of both the road quality and distance, minimizing the road quality first and the distance second. To be able to do this your graph's edges will need to contain a pair. Suppose you're considering an edge to take with road quality of 1, and a distance of 20. If the next edge you're considering has a road quality of 1 as well (equal road quality), then compare the distance. $\endgroup$
    – Logan Leland
    Commented Dec 15, 2016 at 17:53
  • $\begingroup$ I don't really see how that's a modification of Dijkstra's algorithm. How do you propose to do the second pass where you compare different routes of the same "quality"? $\endgroup$
    – David Richerby
    Commented Dec 16, 2016 at 17:25
  • $\begingroup$ It would occur in a single pass $\endgroup$
    – Logan Leland
    Commented Dec 16, 2016 at 18:18
0
$\begingroup$

Instead of considering some of the costs first you can actually define a function $\mathbb{N} \times \mathbb{N} \longrightarrow \mathbb{N}$ (or $\mathbb{R}$ if you're using real numbers) that converts a cost tuple $(a,b)$ to a scalar weights, then just apply Dijsktra with the scalar weights.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.