Since you know it's a line on the unrolled surface, what you need is the transformation from that surface to the actual surface. Using $r$ for the slope of the cone seems a bit confusing; I'll take the liberty to rename that to $m$ and use $r$ for the distance from the origin as usual.
The opening angle of the cone is $\alpha=\arctan m$. The point $(r\cos\phi,r\sin\phi)$ on the unrolled surface corresponds to the point $(r\sin\alpha\cos(\lambda\phi),r\sin\alpha\sin(\lambda\phi),r\cos\alpha)$ on the cone, where the factor $\lambda$ between the angles in the plane and the angles on the cone is determined by the condition that the circles on the cone have $\sin\alpha$ times the length that they would have in the plane, so we need $\lambda=1/\sin\alpha$.
Now use the polar equation for a line,
$$r=\frac{r_0}{\sin(\phi-\phi_0)}\;,$$
to find the equation of the geodesic on the cone, parametrized by $\phi$:
$$\vec x(\phi)=\frac{r_0}{\sin(\phi-\phi_0)}\pmatrix{\sin\alpha\cos\frac\phi{\sin\alpha}\\\sin\alpha\sin\frac\phi{\sin\alpha}\\\cos\alpha}\;.$$
Here's a plot for $\alpha=\pi/10$, $r_0=1$, $\phi_0=0$.
P.S: Perhaps I should add that while your image of the cone rolled out on a plane shows the cone once, we can continue across the boundaries in your image and keep wrapping around the cone, with the angle on the cone always changing by $1/\sin\alpha$ times the change of $\phi$ in the plane. Since a line subtends exactly an angle of $\pi=(2\pi)/2$ with respect to the origin (unless it's a line through the origin, which would simply map to a straight line through the apex of the cone), every geodesic on the cone wraps around the cone exactly $1/(2\sin\alpha)$ times.
For the case of a start node S and two target nodes X and Y, one could use the following algorithm:
Use Dijkstra's shortest-path algorithm to find the shortest path from S to X and the shortest path from S to Y. If path from S to X is shorter, use Dijkstra's shortest-path algorithm to find the shortest path from X to Y, and follow the paths found from S to X and then from X to Y. Else (if the second path is shorter), find the shortest path from Y to X and follow the paths found from S to Y and then from Y to X.
Since this always uses Dijkstra's algorithm exactly 3 times, it is asymptotically just as efficient as Dijkstra's algorithm.
Note that, as Tyler Olsen and ml0105 point out, if there are in fact a variable number of nodes you need to pass through instead of only 3, this problem is NP-Hard.
Best Answer
The problem of computing the shortest path between two points is known as pathfinding, and there are many exact and approximate algorithms for solving it in a variety of settings. A very commonly used one is the A* search algorithm and its variants.
To use A* search, you first need to discretize your search space into a graph (a navigation mesh). For a two-dimensional space with polygonal obstacles, I believe a suitable discretization would be to take as nodes all corners of the polygons (plus the starting and goal points) and as edges the straight-line paths between them, excluding any paths that would pass through the obstacles (but including the edges of the polygons themselves).
In three dimensions, things get more complicated, as evidenced by the fact that there can be points which are not even reachable via a straight path from any corner point of a polyhedral obstacle.
Ps. The red path in your image is not actually the shortest possible one, as it makes turns at points other than at the corners of the obstacles. In particular, the green path below (which does only turn at corners) is clearly shorter: