random path between two nodes in undirected graph
7 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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 commentaires
Walter Roberson
le 15 Août 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.
Réponses (1)
Chunru
le 15 Août 2021
Modifié(e) : Chunru
le 15 Août 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 commentaires
Voir également
Catégories
En savoir plus sur Undirected Graphs dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!