# matlab: check which lines of a path are used - graphshortestpath

The related problem comes from the power Grid in Germany. I have a network of substations, which are connected according to the Lines. The shortest way from point A to B was calculated using the graphshortestpath function. The result is a path with the used substation ID's. I am interested in the Line ID's though, so I have written a sequential code to figure out the used Line_ID's for each path.

This algorithm uses two for loops. The first for-loop to access the path from a cell array, the second for-loop looks at each connection and searches the Line_ID from the array.

**Question**: Is there a better way of coding this? I am looking for the Line_ID's, graphshortestpath only returns the node ID's.

Here is the main code:

for i = i_entries path_i = LKzuLK_path{i_entries}; if length(path_i) > 3 %If length <=3 no lines are used. id_vb = 2:length(path_i) - 2; for id = id_vb node_start = path_i(id); node_end = path_i(id+1); idx_line = find_line_idx(newlinks_vertices, node_start, ... node_end); Zuordnung_LKzuLK_pathLines(ind2sub(size_path,i),idx_line) = true; end end end

**Note**: The first and last enrty of path_i are area ID's, so they are not looked upon for the search for the Line_ID's

function idx_line = find_line_idx(newlinks_vertices, v_id_1, v_id_2) % newlinks_vertices includes the Line_ID, and then the two connecting substations % Mirror v_id's in newlinks_vertices: check_links = [newlinks_vertices; newlinks_vertices(:,1), newlinks_vertices(:,3), newlinks_vertices(:,2)]; tmp_dist1 = find(check_links(:,2) == v_id_1); tmp_dist2 = find(check_links(tmp_dist1,3) == v_id_2,1); tmp_dist3 = tmp_dist1(tmp_dist2); idx_line = check_links(tmp_dist3,1); end

**Note**: I have already tried to shorten the first find-search routine, by indexing the links list. This step will return a short list with only relevant entries of the links looked upon. That way the algorithm is reduced of the first and most time consuming find function. The result wasn't much better, the calculation time was still at approximately 7 hours for 401*401 connections, so too long to implement.

## Answers

I would look into Dijkstra's algorithm to get a faster implementation. This is what Matlab's graphshortestpath uses by default. The linked wiki page probably explains it better than I ever could and even lays it out in pseudocode!