THE GRAPH FUNCTION DOESN'T CONSIDER WEIGHTS

2022 1 30
2 个回答
回答已采纳
更新时间：2022 2 4
3 次查看（30 天）

0 个投票

Hi to everybody, in my code I am trying to calculate the shortest path from a graph, whose I have explicited all parameters.
But from some checks I have done, it seems like the shortestpath function doesn't consider the weights I have putted in the graph. In fact I have manually specified some extremely high values for some of the edges of my graph so that the shortestpath function should avoid them in its calculation, but it doen't happen. I specify that no negative values are present in the Graph.Edges.Weight array.
Are there some tricks to consider, or some advice you can give me to solve my trouble or to understand why shortestpath function doesn't work properly?
Thanks in advance!

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

 采纳的回答

Christine Tobler
Christine Tobler 2022-1-31
Ran in:

1 个投票

Ran in:
Hard to say what's going wrong without seeing your code. Here's an example where you can see the weights being used to decide on the path:
g = graph([1 2 3], [2 3 1], [1 2 100]);
plot(g, 'EdgeLabel', g.Edges.Weight)
[path, dist] = shortestpath(g, 1, 3)
path = 1×3
1 2 3
dist = 3
[path, dist] = shortestpath(g, 1, 3, 'Method', 'unweighted')
path = 1×2
1 3
dist = 1

5 个评论
显示 3更早的评论 隐藏 3更早的评论

Gianluca Angelini
Gianluca Angelini 2022-1-31
The code is as simple as that in your example... The only difference is in the number of elements conisdered (but i think it should not create any problem), since s-, t- and weights-arrays from the expression g = graph(s, t, weights) have more or less 400000x1 elements.Indeed I have tried to plot the graph taking into account only part of the arrays, and I have something like this:
Christine Tobler
Christine Tobler 2022-1-31
编辑：Christine Tobler 2022-1-31
The length of the inputs really shouldn't matter.
The first thing you might consider is whether, when those edges you gave extremely high values to are removed, there is still any other path that avoids those edges. You could check this by using rmedge to remove all those edges from the graph, and then call shortestpath again and see if any path is found.
Also, what result are you getting for the length of the path (second output of shortestpath). Is it Inf by any chance?
Gianluca Angelini
Gianluca Angelini 2022-1-31
Hi Christine, I have just tried to follow your suggestions.
By using rmedge, shortestpath function returns an empty value of path and Inf for the lenght of the path consequently.
Christine Tobler
Christine Tobler 2022-1-31
All right, so in that case shortestpath was using these edges with extremely high values because there is no path connecting the two input nodes that doesn't pass through these edges.
Thanks for your support.
I will maintain the line with the rmnedge function in my code in order to avoid the edges with high weights.

请先登录，再进行评论。

更多回答（1 个）

Steven Lord
Steven Lord 2022-1-30

0 个投票

Are you representing your graph as a graph or digraph object or as a biograph object?
How have you stored / represented your weights? If a graph or digraph does your object's edges table G.Edges contain a variable named Weight? [Weights won't do, it must be named exactly Weight.]
What algorithm did you tell shortestpath to use in determining the shortest path? If you're using a biograph did you specify BFS as the method?

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Gianluca Angelini
Gianluca Angelini 2022-1-30
I confirm I have used the graph object and its weights are stored in a G.Edges.Weight array.
Concerning the shortestpath, I have used this:
shortestpath(G,start_id,finish_id,'Method','positive');

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

产品

版本

R2018b

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by