Shortest distance Definition and 72 Threads

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between two intersections on a road map may be modeled as a special case of the shortest path problem in graphs, where the vertices correspond to intersections and the edges correspond to road segments, each weighted by the length of the segment.

View More On Wikipedia.org
Recent contents Top users
  1. brotherbobby

    B Shortest distance between two points

    I copy and paste the diagram I drew for the problem to the right. The two points in question are A and B. The vertical from B is ##d## units long and is ##s## units away from A. What is the shortest way to go from A to B? We expect it to be a distance of (say) ##y=\sqrt{s^2+d^2}##. Thus, if...
  2. chwala

    Find the shortest distance between the given vectors in 3D

    This is a textbook problem...the only solution given is ##3.##...with no working shown or given. My working is below; i just researched for a method on google, i need to read more in this area...use of the directional vector may seem to be a more solid approach. Ok i let ##A=(6,-4,4)##...
  3. M

    How to prove that the shortest distance between two points is a line?

    I tried using hamilton method but i don't think that's correct
  4. Poetria

    The shortest distance (gradients)

    I got: $$(\frac {1} {\sqrt \frac {5}{0.01}}, \frac {2} {\sqrt \frac {5} {0.01}})$$ The approximate value of the function = -0.55 The exact value of the function = -0.998 Well, the vector and the exact values of the function aren't correct but I don't know why. Any hint?
  5. Baums Mizushala

    Point on a graph nearest to the origin

    The Attempt at a Solution I know the answer is supposed to be ##(-1,0)##. However when I differentiate the above expression I get. $$ 2x+{\frac 5 2} $$ Then the shortest distance would be when the expression equates to 0. $$ 2x+{\frac 5 2}=0 $$ I should be getting ##x=-1## but solving for ##x##...
  6. karush

    MHB APC.3.1.2 shortest distance between curve and origin

    Find the x-coordinate of the point on $f(x)=\dfrac{4}{\sqrt{x}}$ that is closest to the origin. a. $1$ b. $2$ c $\sqrt{2}$ d $2\sqrt{2}$ e $\sqrt[3]{2}$ not real sure but, this appears to be dx and slope problem I thot there was an equation for shortest distance between a point...
  7. Specter

    Finding the shortest distance from a point to the plane

    Homework Statement Find the shortest distance from P(-4,2,6) to the plane 2x-3y+z-8=0. Homework Equations ##|proj_\vec n \vec PQ|=|(\frac {\vec PQ \cdot \vec n} {\vec n \cdot \vec n})| |\vec n|## The Attempt at a Solution I kind of had to guess some steps because it was done differently in...
  8. Krushnaraj Pandya

    Vector of shortest distance between two skew lines

    Homework Statement how to write the vector equation of the line of shortest distance between two skew lines in the shortest and most efficient way? (The exact lines given in a particular problem in my book can be referenced- L1=(3i+8j+3k)+λ(3i-j+k) and L2=(-3i-7j+6k)+μ(-3i+2j+4k) ) 2. Relevant...
  9. K

    Min Max problem: the shortest distance for a light ray

    Homework Statement Homework Equations Minimum/Maximum occurs when the first derivative=0 GM≤AM: ##~\sqrt{xy}\leq\frac{x+y}{2}## The Attempt at a Solution [/B] If the sum of squares of the distances (setup 2) in an arbitrary point is bigger than the sum of the squares of the shortest...
  10. C

    MHB [Linear Algebra] - Find the shortest distance d between two lines

    Let L1 be the line passing through the point P1=(−2,−11,9) with direction vector d2=[0,2,−2]T, and let L2 be the line passing through the point P2=(−2,−1,11) with direction vector d2=[−1,0,−1]T Find the shortest distance d between these two lines, and find a point Q1 on L1 and a point Q2 on L2...
  11. H

    Shortest distance between a line and a point?

    Homework Statement find the shortest distance from (0,0) to the line passing A(2,3) and B(3,5) Homework Equations ## \frac{y-y1}{y2-y1} = \frac{x-x1}{x2-x1} ## y-y1 = m (x-x1) m1 * m2 = -1 (m1 perpendicular to m2) The Attempt at a Solution line passing A and B points ## \frac{y-3}{5-3} ## =...
  12. A

    A Shortest distance scales that a string can resolve

    On page 5 of the notes (https://arxiv.org/abs/1501.00007) by Veronika Hubeny on The AdS/CFT correspondence, we find the following: Nevertheless, already at this level we encounter several intriguing surprises. Since strings are extended objects, some spacetimes which are singular in general...
  13. M

    Prove the shortest distance between two points is a line

    Homework Statement Let γ : [0, L] → Rn be arclength parametrized. Show that the distance between the endpoints of the curve can at most be L, and equality can only hold when γ is a straight line segment. Thus, the shortest path between two points is the straight line segment connecting them...
  14. ChrisisC

    B Curved line shortest distance between two points?

    Can someone explain how this is possible? it makes no sense to me. You wouldn't walk along the track surrounding a soccer field if you wanted to get to the other end... you would walk straight across the grass to reach your destination. Why did Einstein propose this?
  15. A

    I Which Is More Fundamental: Time or Distance?

    Is the following logic correct? When spacetime is flat, we say that light travels in a straight line. A planet also would travel in a straight line because that would take the shortest travel time between two points. Does light seek out the shortest time to travel between two points, or the...
  16. RoboNerd

    I Finding shortest distance between skew lines, checking work.

    Hi everyone. I was working on a problem for days. The problem statement is: "Consider points P(2,1,3), Q(1,2,1), R(-1,-1,-2), S(1,-4,0). Find the shortest distance between lines PQ and RS." Now, I did the following formula: PS dot (PQ x RS) / magnitude of (PQ x RS). (For skew lines) Now...
  17. karush

    MHB Shortest distance between (18,0) and y=x^2

    What is the shortest distance between $(18,0)$ and $y=x^2$ I presume this could be solved by slopes but couldn't get the formula set up
  18. J

    A check: shortest distance from point to line

    We want to know the shortest distance from the point P to the line (see figure 1). As far as I know it is given by the length of the segment perpendicular to the line that joins the line to the point. Can you check this argument I give is correct? Part A. First let us draw in the segment from...
  19. T

    Shortest Distance Between Two Latitude/Longitude Coordinates

    Homework Statement We need to find the shortest distance between two given cities. For this I'll use Bangkok, Thailand (13°N, 100°E) and Havana, Cuba (23°N, 82°W ). Earth is assumed to be perfectly spherical with a radius of 6.4x106m. These aren't the places we were given but the coordinates...
  20. ognik

    MHB How does using cross product to find shortest distance work?

    A method for finding the shortest distance between 2 skew, non intersecting lines is to 1st find the common normal, using $ \vec{n} = \frac{\vec{v_1} \times \vec{v_2}}{|\vec{v_1} \times \vec{v_2}|} $ I'm looking for a proof or intuition as to why this is true please? Then apparently we get the...
  21. RJLiberator

    How to find the shortest distance to a hyperboloid, etc?

    Homework Statement Consider the hyperboloid of two sheets: z^2=x^2+y^2+1 and a point P(0, 1, 0). Find the shortest distance between the hyperboloid and the point P. Also, find coordinates of all points on the surface for which this distance is attained. Homework EquationsThe Attempt at a...
  22. G

    Formula of shortest distance between two skewed lines

    Homework Statement kindly refer to the yellow highlighted part, why is but not ? Homework EquationsThe Attempt at a Solution
  23. admbmb

    Finding Shortest Distance between two 3d Parametrized Curves

    So I have two parametrized equations for two different 3d curves: Rm(t) = (1.2*sin(2πt) + 0:3)i + t4j + 1.1cos2(2π(t + 0:2))k and R(t) = Sin(2πt)i + t3j + Cos2(2πt)k I need to figure out if these two curves come within a certain distance of each other (0.5). I cannot understand how to find...
  24. D

    Shortest distance light wave can travel?

    Hey i wanted to know if this answer is already present.If yes then what is the shortest amount of distance a beam of light can travel?
  25. Adjoint

    Shortest distance between two cars

    Homework Statement Two straight roads, which are perpendicular to each other, cross at point O. Suppose a car is at distance 250m from the origin on one road, and another car is at distance 350m from the origin on another road. Both cars are approaching towards the origin. The...
  26. karush

    MHB Shortest distance between line and point

    Show that the shortest distance from the point $\left(x_1,y_1\right)$ to a straight line $$Ax_1+By_1+C=0$$ is $$\frac{|Ax_1+By_1+C|}{\sqrt{A^2+B^2}}$$ ok, well a line from a point to a line is shortest if it is perpendicular to that line obviously we are trying to find out a min value to...
  27. M

    Shortest distance from A to B to C?

    Homework Statement You are standing on an open field 72,0 m away from a straight river. Your tent is 136 m away from you, while being only 8,0m away from the river (on the same side you are on). Before you go back to your tent, you would like to fill your water bottle in the river. What point...
  28. N

    Shortest distance between point and line.

    [b]1. Shortest distance between: 5x^2 - 6xy + 5y^2 = 4 and origin. [b]2. d = sqrt(x^2 + y^2) [b]3. d = sqrt[(4+6xy)/5]. Can't figure out how to get an explicit equation in x or y. This is a first semester calculus problem out of Thomas from my 1971 class. This is indepent study.
  29. C

    Determine shortest distance a car could stop without causing serious injury

    Homework Statement It may be assumed that the human body can withstand an acceleration of 3g's without sustaining serious injury. A person is driving a car at 60 miles per hour. Determine the shortest distance such that the car could be brought to a stop (at constant acceleration) without...
  30. N

    Calc III: Shortest Distance in 3D Problem

    Calculus III, find shortest distance, 3 dimension problem? check my answer please?? What is the shortest distance from the point P = (0, 1, 2) to the line given by l(t) = (1+t, 2-2t, 3+3t)? use distance formula d = sqrt ((x-0)^(2) + (y-1)^(2) + (z-2)^(2)) d^(2) = ((x)^(2) + (y-1)^(2) +...
  31. V

    Python BFS Shortest Distance of Graph Calculation in Python

    Homework Statement I have this problem essentially figured out. There's just one tiny problem that I can't seem to solve. I'm supposed to write a function bfs(G, v) which takes a graph G stored as a dictionary, and a starting vertex v. The function bfs performs a breadth-first-search...
  32. andrewkirk

    Is the proper distance the shortest distance in FLRW universe?

    In Appendix A of Davis & Lineweaver (2003) proper distance to a faraway galaxy is defined as the distance along a curve of constant time in the RW metric. I was wondering whether that line of constant time is a geodesic of spacetime. If not then there will be a shorter-distance path from here...
  33. E

    Shortest distance between lines and the lines

    Homework Statement Find the shortest distance between the lines r = (0,7,6) + t (-3,2,2) and the line r = (-3,6,-4) + s (2,-5,6) The Attempt at a Solution What I did was I cross product s(2,-5,6) & t(-3,2,2) then I took (0,7,6) - (-3,6,-4) After getting both answer from the 2 steps I took...
  34. A

    Shortest Distance in Euclidean Geometry: Proven or Definition?

    In euclidean geometry I believe the shortest distance is the perpendicular one. Can this be proven or is it a definition?
  35. T

    Find shortest distance from a point along a vector to a plane

    Homework Statement The vector from the origin, O, to point P has magnitude 60 m and has equal direction angles with the x, y, and z axes. Find the shortest distance from point P to the plane containing points A, B, and C. A (12,0,0) B (0,16,0) C (0,0,9) Homework Equations N/A The Attempt...
  36. M

    Longest and shortest distance in an elliptical orbit

    Homework Statement Two satellites are launched at a distance R from a planet of negligible radius. Both satellites are launched in the tangential direction. The first satellite launches correctly at a speed v0 and enters a circular orbit. The second satellite, however, is launched at a speed...
  37. T

    Shortest Distance between 2 convex sets

    Hi, I hope someone can help me out with this problem: Let set S be defined by (x in En :f(x) <=c} f: En -> E1 is convex and differentiable and gradient of f(xo) is not 0 when f(x) = c. Let xo be a point such that f(xo) = c and let d = gradient at xo. Let lamda be any positive number and...
  38. T

    Shortest Distance between 2 skew lines (vectors)

    Homework Statement x1 = (0,0,4) + s(2,0,-1) x2 = (-4,2,2) + t(-5,1,1) Homework Equations The Attempt at a Solution First of all I find the common perpendicular (vector cross product) Make it unit Find a arbitrary line joining the two 2 lines (set s = t= 0) Then scalar...
  39. G

    Shortest distance between A(2,1,-2) and the line x=3-2t;y=-4+3t;z=1+2t.

    Homework Statement Find the shortest distance between A(2,1,-2) and the line having parametic equations: x=3-2t; y=-4+3t; z=1+2t. Homework Equations After derivation: d = |AB| sin( arccos( (AB.BC)/|AB||BC| ) ) B and C are points on the line found by putting random values for t. For t=0 ->...
  40. A

    Shortest distance you can travel?

    What is the shortest distance you (or anything) and travel? Is there a limit? And if so why?
  41. P

    Shortest distance between plane and point

    Homework Statement Given the equation of the plane to be: P = 0 + a[1,1,1]^T + b[x1,x2,x3]^T and the point Y = [y1, y2, y3]^T Show: (F)^T(Y-F)=0, where F is the point on the plane closest to Y Homework Equations The Attempt at a Solution Y = F + FY Y - F = FY...
  42. E

    Calculus of Variations: Shortest distance between two points in 3D space

    Homework Statement Show that the shortest distance between two points in three dimensional space is a straight line. Homework Equations Principally, the Euler Lagrange equation. The Attempt at a Solution I understand how to do this for a plane, but when we move into three...
  43. S

    Find the shortest distance between two lines:

    Given the following two skew lines: L1: (0, 4, -3) + s(-1, 1, 3) L2: (1, 2, 5) + t(-3, 2, 5) Find the shortest distance. MY WORK:: Cross-product of the lines (-1, 1, 3) X (-3, 2, 5) = (-1, -4, 1) with length 3*sqrt(2) Vector between the points (0, 4, -3) - (1, 2, 5) = (-1, 2, -8)...
  44. jegues

    Shortest distance between 2 curves

    Homework Statement Find the shortest distance between, y = x^{2} - 8x + 15 and, 2y + 7 + 2x^{2} = 0 Homework Equations The Attempt at a Solution Rearranging the 2nd function into a function of y in terms of x, y = -x^{2} - \frac{7}{2} From here I was able to graph...
  45. R

    How to Find the Shortest Distance to the Brillouin Zone Boundary?

    Hi, I just can't understand the basics with BZ. How do I find the shortest distance to the BZ boundary, how do I compare the electron energy between the last electron in the 1st BZ with the first electron in the 2nd BZ? I think I need a visual how to calculate these things, does anyone...
  46. A

    Shortest distance between two lines

    I'm a bit uncertain about this question and would like some help, as I don't have the correct answer. Have I done this correctly? Homework Statement What is the shortest distance between the two lines A = (1,2,3) + t(0,1,1) and B = (1,1,1) + s(2,3,1) The Attempt at a Solution My...
  47. C

    Line of sight vs. 90degree shortest distance

    I am working on a project in which I need to know how high voltage arcing occurs. Will arc travel the line of sight path or will it take the shortest distance which has the 90degree angle? What is the reasoning behind the path that it chooses and does anyone have any websites or articles that...
  48. E

    What Is The Shortest Distance Between Two Thoughts?

    Can anyine get this one, it is some what of a philosophical riddle.
  49. A

    Use lagrange multipliers to find the shortest distance

    Homework Statement Use lagrange multipliers to find the shortest distance between a point on the elliptic paraboloid z=x^2 +y^2 Homework Equations The Attempt at a Solution http://img716.imageshack.us/img716/7272/cci1902201000000.jpg I'm not that good with using the equation...
  50. N

    Shortest distance between two points is a straight line in non-Euclidean metric

    Homework Statement Consider the metric in polar coordinates ds=\frac{2}{1-r^2}\sqrt{dr^2+r^2d\phi^2} Show that the shortest path from the origin to any other point is a straight line. Homework Equations Euler-Lagrange equations \frac{\partial F}{\partial y} - \frac{d}{dx}\frac{\partial...
Back
Top