Why the command "graphallshortestpaths" gives me Inf value for a weighted indirect graph that I know it doesn't have disconnections?
9 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
Jorge Pesantez
le 15 Sep 2016
Réponse apportée : Christine Tobler
le 16 Sep 2016
I am trying to get the shortest path of all the nodes of a network for a weighted non-negative sparse matrix. When I use "graphallshortestpath", I get some "Inf" values that indicates there is no path between 2 nodes. I tried the same graph with a dense matrix and used Dijkstra's algorithm and I had no "Inf" values at all. So, I don't know why "graphallshortestpath" built in function -that is much more faster because works with sparse matrix- is giving me "Inf" values.
Any ideas, please.
Thanks,
1 commentaire
Christine Tobler
le 16 Sep 2016
Could you post an example of the graph you are using? I tried an example and I don't see this happening for that case:
>> M = sparse([1 3], [2 4], 1, 4, 4);
>> graphallshortestpaths(M)
ans =
0 1 Inf Inf
Inf 0 Inf Inf
Inf Inf 0 1
Inf Inf Inf 0
>> graphshortestpath(M, 1,'Method','Dijkstra')
ans =
0 1 Inf Inf
Réponse acceptée
Christine Tobler
le 16 Sep 2016
I'm not sure what function you are using to compute Dijkstra with a dense matrix - graphshortestpath for a dense matrix returns an error for me.
I would assume that the problem is that when a graph is represented as a sparse matrix, the assumption is that all zeros stand for edges that do not exist. But when you use a dense matrix, the algorithm might be interpreting every zero entry as an edge with length zero - so every node would be reachable from every other node.
0 commentaires
Plus de réponses (0)
Voir également
Catégories
En savoir plus sur Dijkstra algorithm dans Help Center et File Exchange
Produits
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!