IVILPIT LIOICE 1 point possible (graded) What does the statement \"subpaths of s

Question

IVILPIT LIOICE 1 point possible (graded) What does the statement "subpaths of shortest paths mean?" • If I know how to get from a tob via a path p, all points on the path are closer to each other than a is to b • If the shortest path from a to b goes through x, then it consists of the shortest path from a tox followed by the shortest path from X to b. • Path shorter than shortest paths are optimal. You have used 0 of 1 attempt Ra Multiple Choice 1 point possible (graded) The triangle inequality states that in a triangle, the length of one edge is always less than the sum of the other two. That is, in a triangle with vertices x and y and z, and edge lengths described by a distance function d(), we have d(xy) + d(zy). The idea of the triangle inequality can be extended to more points. Which is a correct generalization of the triangle inequality to four points: 0 d(a,b) + d(b,c) >= d(a,) - d(ce) 0 d(a,b) + d(b,c) >= d(G,e) + d(a,e) 0 d(a,b) - d(b,c) >= d(ce) - d(a,e)

Explanation / Answer

1) The answer is A and B.

A: The distance from any two points on the path will also be computed by adding the weights of the edges between them, but all the edges between those two points will also be present in the path from a to b. But path from a to b will also consist of some more edges which are not covered in the path betwene those two points. Hence any two points in the path are closer then a and b.

B: If the given statement is false. Then assume a to x or x to b has another shortest path. Then the path we have chosen in the first place as shortest path from a to b, is not true. Hence by condration the paths a to x and x to b must be shortest.

2) The answer is A.

We have four points a,b,c,e.

We know d(a,b) + d(b,c) > d(a,c)

d(a,c) + d(c,e) > d(a,e)

Adding them

d(a,b) + d(b,c) + d(c,e) > d(a,e)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.