efficient tree traversal in effort to solve k-shortest path problem

I've been trying to find a way to efficiently solve the k-shortest path problem. There is a code online that implements Yen's algorithm, but it takes input as an adjacently matrix with inf to mark disconnected nodes. I have over 10^6 nodes, so this requires a dense matrix with 10^12 entries, which is impractical. I tried implementing Yen's algorithm myself using the graph class, but it is very slow because of all the time spent removing edges from the graph. I then thought maybe a method based on the shortestpathtree would be more efficient. I can compute this tree in 0.3s but a single traveral of the tree takes 5s.

Is there an efficient way to traverse the tree? It's not much use to generate the tree if I can't actually use it for anything. It seems like in general the functions that actually find and operate on nodes and edges are very slow. I traversed the tree by invoking predecessor repeatedly. Is there another approach that is faster?

Alternatively, is there a better way to solve the k-shortest path problem?

Answer 1

[Hari]

Hi Adrian Mariano,

I understand you want an efficient method to solve the k-shortest path problem in a graph with over 10^6 nodes. You have noticed that traversing a shortest path tree is slow, particularly when using the "predecessor" function repeatedly.

I assume that you are looking for a solution within MATLAB environment, focusing on efficiency both in terms of memory and computation time

Here are some of the ways to acheive Efficient Tree Traversal:

1. Optimizing Tree Traversal: Instead of using the "predecessor" function repeatedly, consider storing the tree in a more traversal-friendly structure once it's computed. For example, you could map each node to its children in a hash table or dictionary structure, allowing for more efficient traversal without repeated lookups.
2. Batch Processing: When possible, perform operations on batches of nodes or edges instead of individual ones. MATLAB operations are generally more efficient when vectorized or when operating on larger data sets at once, rather than looping through individual elements.
3. Graph Representation: For handling large graphs, consider using sparse matrices or adjacency lists if your graph is sparse, which it likely is with over 10^6 nodes. Sparse matrix operations in MATLAB are optimized for memory efficiency and speed, which could alleviate the issues with using dense matrices.

Alternative Approaches for k-Shortest Paths:

1. Eppstein's Algorithm: Eppstein's algorithm is another method for finding k-shortest paths that might offer better performance for certain types of graphs, especially sparse ones.
2. Heuristic Methods: For very large graphs, exact methods become impractical, and heuristic or approximation algorithms might provide a good balance between accuracy and computational requirements. Techniques such as A* search with well-chosen heuristics can significantly reduce the search space.

References:

• For information on MATLAB's graph and network algorithms, refer to the documentation of graph and digraph classes: https://www.mathworks.com/help/matlab/graph-and-network-algorithms.html.
• For optimizing performance in MATLAB, especially with large data sets, see: https://www.mathworks.com/help/matlab/matlab_prog/techniques-for-improving-performance.html.
• MATLAB's sparse matrices documentation for efficient storage and manipulation of large, sparse graphs: https://www.mathworks.com/help/matlab/sparse-matrices.html.

Hope this helps!

Answer 2

[Adrian Mariano]

It's been a few years since I asked that question. I ended up needing a variety of different heuristic graph algorithm and my conclusion in the end was that all the graph algorithms need an efficient priority queue, which is impossible to implement in MATLAB but is available as a data type in Java, which MATLAB uses. I ended up doing all of my graph analysis with Java code that I could then call from MATLAB.