random path between two nodes in undirected graph
7 ビュー (過去 30 日間)
古いコメントを表示
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 件のコメント
Walter Roberson
2021 年 8 月 15 日
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.
回答 (1 件)
Chunru
2021 年 8 月 15 日
編集済み: Chunru
2021 年 8 月 15 日
% 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 件のコメント
参考
カテゴリ
Help Center および File Exchange で Undirected Graphs についてさらに検索
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!