Why the command "graphallshortestpaths" gives me Inf value for a weighted indirect graph that I know it doesn't have disconnections?

Question

Jorge Pesantez 2016-9-15

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/303197-why-the-command-graphallshortestpaths-gives-me-inf-value-for-a-weighted-indirect-graph-that-i-know

回答： Christine Tobler 2016-9-16

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 个评论
显示 -1更早的评论隐藏 -1更早的评论

Christine Tobler 2016-9-16

在 MATLAB Online 中打开

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

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Christine Tobler 2016-9-16

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/303197-why-the-command-graphallshortestpaths-gives-me-inf-value-for-a-weighted-indirect-graph-that-i-know#answer_235026

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.