Shortest Path Algorithm

Question

I am trying to implement a shortest path algorithm into my code, but I am at a loss on how to do it. Suppose you had a matrix that contained the (x,y) coordinates of several line segments. Suppose that each line segment had a score associated with it, and the score indicates how "valuable" that line segment is to a design.

If this information was put into a matrix the rows could be formatted as follows:

Start X, Start Y, End X, End Y, Score

Now, suppose that there is no connectivity information provided in the above matrix, i.e. you do not know the relation of 1 line to another based on the matrix. Based on the matrix above, I want to find the element path the produces the highest score (in my program it is the lowest score, but this is semantics). The catch, however, is that each path must be continuous with no jumps between connecting line segments. Does anyone know how to code this? I have a segment of my code below where the score of each element is calculated and stored (in the matrix ElementMap), but I don't know how to form the optimal path once I have ElementMap.

Thanks

for i = 1:Count2
 for j = 1:length(ElementMap)

    xStart = ElementMap(j,1);
    yStart = ElementMap(j,2);
    xEnd = ElementMap(j,3);
    yEnd = ElementMap(j,4);

    Score = 0;
    if NodeMap(2*(i-1)+1) == ElementMap(j,1) && ElementMap(j,5) ~= 1

        for m = 1:length(ThetaIncident)

            [Point] = RayScore(xStart,yStart,xEnd,yEnd,ThetaIncident(m),OvenGlassXrange);

            Score = Score - Point;
        end
        ElementMap(j,5) = 1;  % 1 will indicate Element has been analyzed
    end
    ElementMap(j,6) = ElementMap(j,6) + Score;
 end
end

I would solve it in two steps: 1. create a graph out of the endpoints (i.e., every unique endpoint is a vertex and every segment is a weighted edge connecting two vertices), 2. run the appropriate graph algorithm — Vincent van der Weele
– Vincent van der Weele, Commented Aug 1, 2016 at 19:22
I understand the concept of a shortest path algorithm, but the part I am having trouble with is implementing one within the context of my code. — Grady F. Mathews Iv
– Grady F. Mathews Iv, Commented Aug 2, 2016 at 14:52
You seem to have skipped step 1 in @VincentvanderWeele's suggestion. Presumably you have some set of unique coordinates (x,y). Each unique coordinate is a vertex. Each row of your data is an edge. Does that make sense? — beaker
– beaker, Commented Aug 2, 2016 at 15:16
This does make sense, but I have some questions. Essentially what is needed to make a graph are several paths that are defined as a collection of edges. With my data only certain edges will geometrically connect with each other (form a continuous function), and I don't know how to tell which combination of edges will form a viable path. How do I form the paths? — Grady F. Mathews Iv
– Grady F. Mathews Iv, Commented Aug 2, 2016 at 15:58

Toothpick Anemone · Accepted Answer · 2016-08-04 06:48:41Z

It sounds to me like you start out with an array like this one:

+---------+---------+-------+-------+-------+
| Start X | Start Y | End X | End Y | Score |
+---------+---------+-------+-------+-------+
| 1       | 3       | 2     | 4     | 23    |
+---------+---------+-------+-------+-------+
| 1       | 3       | 7     | -3    | 87    |
+---------+---------+-------+-------+-------+
| 7       | -3      | 5     | 5     | 12    |
+---------+---------+-------+-------+-------+

Before you go about trying to find a shortest path, I would recommend that you write code which does some preliminary work. I would suggest that you first create a new/separate array to represent the x-y- coordinate pairs which are your line segments' end points.

Using the same example data I gave above, we have:

+---+----+
| X |  Y |
+---+----+
| 1 | 3  |
+---+----+
| 2 | 4  |
+---+----+
| 7 | -3 |
+---+----+
| 5 | 5  |
+---+----+

Next, arbitrarily name/index these points

+---------+---+----+
| pointID | X |  Y |
+---------+---+----+
| 1       | 1 | 3  |
+---------+---+----+
| 2       | 2 | 4  |
+---------+---+----+
| 3       | 7 | -3 |
+---------+---+----+
| 4       | 5 | 5  |
+---------+---+----+

Optionally, you can consider the original table in terms of pointIDs instead of x and y coordinates. It is not necessary to write code to do this, but it can be done by hand with a small example in order to aid in conception.

+--------------+------------+-------+
| StartPointID | EndPointID | Score |    
+--------------+------------+-------+
| 1            | 2          |  23   |
+--------------+------------+-------+
| 1            | 3          |  87   |
+--------------+------------+-------+
| 3            | 4          |  12   |
+--------------+------------+-------+

Now, construct a matrix where the entry in the ith row and jth column is the score associated with the line segment which starts at the point with index i and ends at the point which is indexed as j.

    ╔═════╦═════╦═════╦═════╗
    ║ 1   ║ 2   ║ 3   ║ 4   ║
╔═══╬═════╬═════╬═════╬═════╣
║ 1 ║ N/A | 23  | 87  | N/A |
╠═══╬-----+-----+-----+-----+
║ 2 ║ 23  | N/A | N/A | N/A |
╠═══╬-----+-----+-----+-----+
║ 3 ║ 87  | N/A | N/A | 12  |
╠═══╬-----+-----+-----+-----+
║ 4 ║ N/A | N/A | 12  | N/A |
╚═══╩-----+-----+-----+-----+

With this last array in hand (by the way, this is called an adjacency matrix), you are now ready to find a shortest path for your edge-weighted graph.

Collectives™ on Stack Overflow

Shortest Path Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related