Pathfinder

Suppose you have a network of connected points on a plane. It may not be fully connected, but it is possible to get from one point to any other point. If you found the shortest route from a starting point to every other point, which of these routes is the longest?

More formally, given the adjacency matrix a and the coordinates matrix b, find the path from the first point in b (given by the first row in b) to the most distant point from b as traveled through the minimal network distance.

Coordinates in b are provided in the form [x1 y1; x2 y2; ...]. Travel is permitted only between connected points as indicated by ones in the adjacency matrix a. Return your answer c in the form of a vector of indices that represent the waypoints from start to finish. c(1) will always be one.

So when

 a = [ 1     1     0
       1     1     1
       0     1     1 ]

and

 b = [ 0     0
       1     0
       1     1 ]

the most distant point from point 1 (x1,y1) is point 3 (x3,y3), a total distance of 2 away. Since point 1 is not directly connected to point 3, the trip must include point 2. Return

c  = [ 1 2 3 ]

If a had been the fully connected matrix ones(3), then the answer would have been

c = [ 1 3 ]

Since there would no longer be a need to detour through point 2.

A slightly more complex problem appears below.

a = [ 1     0     1     0     0     0
      0     1     1     1     0     0
      1     1     1     1     0     0
      0     1     1     1     1     1
      0     0     0     1     1     0
      0     0     0     1     0     1 ]

b = [ 0     0
      1     2
      1     1
      2     2
      3     0
      3     3 ]

Even if you take the shortest path from point 1 to point 5, it ends up being harder to reach than any other point in the network. What is the shortest path to point 5?

c = [ 1 3 4 5 ]

Leaders