random path between two nodes in undirected graph
5 views (last 30 days)
Show older comments
I have a graph which consists of nodes and I need a fast algorithm that generates a random path between two nodes. I designed several algorithms from scratch for this but can't seem to get it right.
Either the algorithm gets stuck in loops, or when I keep record of the visited nodes it sometimes gets stuck between visited nodes. Another problem I encountered is that my algorithm was too unstable in performance.
So my question is; does anyone know a fast and stable algorithm for a random path between two reachable nodes in an undirected graph?
2 Comments
Walter Roberson
on 15 Aug 2021
Oddly, your question is word-for-word identical to https://stackoverflow.com/questions/10198198/whats-a-fast-and-stable-algorithm-for-a-random-path-in-a-node-graph from 9 years ago.
Answers (1)
Chunru
on 15 Aug 2021
Edited: Chunru
on 15 Aug 2021
% Generate a graph
s = [1 1 1 2 2 3 3 4 5 5 6 7];
t = [2 4 8 3 7 4 6 5 6 8 7 8];
G = graph(s,t);
h=plot(G)
% find all paths between two nodes
p = allpaths(G, 2, 5); % nodes 2 and 5
npath = length(p);
% random path
idx = randi([1 npath], 1);
p{idx}
highlight(h,p{idx},'NodeColor','g','EdgeColor','g')
0 Comments
See Also
Categories
Find more on Undirected Graphs in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!