Do you want to visit each node exactly once, or would it be okay to visit some of the nodes twice, as long as each node is visited at least once? Also, is your graph directed or undirected?
graphshortestpath function visiting all nodes
11 次查看（过去 30 天）
显示 更早的评论
Hi,
Is there a way I can manipulate this function in order to force the path include all nodes? I mean, how can I change the code in order to include each node to find the shortest path , but with the constrain that we must visit all nodes?
Thank you in advance
3 个评论
Jason
2018-3-6
编辑：Walter Roberson
2018-3-6
W
= [5 1 5 4 6 1 1 4 7 2 6 7 3 2 1 2 3 8 2 8];
DG = sparse([1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6],[2 3 1 3 4 5 1 2 4 5 2 3 5 6 2 3 4 6 4 5],W)
h = view(biograph(DG,[],'ShowWeights','on'))
[dist,path,pred] = graphshortestpath(DG,1,6)
set(h.Nodes(path),'Color',[0 1 1])
edges = getedgesbynodeid(h,get(h.Nodes(path),'ID'));
set(edges,'LineColor',[0 0 1])
set(edges,'LineWidth',2)
I am implementing the above code, as I understand this function examines the shortest path among all the nodes.
I want to manipulate the code in order to visit all the nodes and outputs a graph that has visited all the nodes with the minimum distance.
采纳的回答
更多回答（2 个）
Christine Tobler
2018-3-6
As Steve Lord has said, in general this is an NP-complete problem, so could become quite expensive. For the 6-node graph you are looking at, this is easy to compute using an exhaustive search (I will use the graph object instead of the bioinfo variants here):
W = [5 1 5 4 6 1 1 4 7 2 6 7 3 2 1 2 3 8 2 8];
DG = sparse([1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6],...
[2 3 1 3 4 5 1 2 4 5 2 3 5 6 2 3 4 6 4 5],W);
g = graph(DG);
% Construct all possible ways that we could traverse all nodes, starting at
% node 1 and ending at node 6:
paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths 6*ones(size(paths, 1), 1)];
% Check if a path is feasible (edges exist between all node pairs), and how
% long it is
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
path = paths(ii, :);
edgeID = findedge(g, path(1:end-1), path(2:end));
if all(edgeID ~= 0)
dist(ii) = sum(g.Edges.Weight(edgeID));
end
end
[~, id] = min(dist)
paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, paths(id, :), 'EdgeColor', 'red')
28 个评论
Jason
2018-3-6
Thanks for the quick repsonse Christine!
I' ll test what you coded there and give feedback.
In the meantime, I want to ask if I can implement this 6 node graph using the TSP (solver/problem based solution).
Thank you again!
Jason
2018-3-6
I change the W and DG and I get this
Error using graph (line 227) Adjacency matrix must be symmetric.
The new W and DG are:
W = [3 1 5 4 1 5 4 3 5 4 2 1 3 1 3 3 5 2 4 1]
and
DG = sparse([1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5],... [2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4],W);
Respectively. I also change the paths = perms(2:5); to 2:4
and
paths = [ones(size(paths, 1), 1) paths 6-> 5*ones(size(paths, 1), 1)]
Steven Lord
2018-3-7
Do you have an undirected graph or a directed digraph? If your network is undirected and you try to construct the graph using the adjacency matrix input A, that input must be symmetric or you must specify the TYPE input when constructing your graph.
Jason
2018-3-7
编辑：Jason
2018-3-7
Well it is a directed graph.It has 5 nodes instead of 6. check it out.
W = [3 1 5 4 1 5 4 3 5 4 2 1 3 1 3 3 5 2 4 1];
DG = sparse([1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5],...
[2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4],W);
g = graph(DG);
% Construct all possible ways that we could traverse all nodes, starting at
* *% node 1 and ending at node 6**:
paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths 6*ones(size(paths, 1), 1)];
% Check if a path is feasible (edges exist between all node pairs), and how
% long it is
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
path = paths(ii, :);
edgeID = findedge(g, path(1:end-1), path(2:end));
if all(edgeID ~= 0)
dist(ii) = sum(g.Edges.Weight(edgeID));
end
end
[~, id] = min(dist)
paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, paths(id, :), 'EdgeColor', 'red')
Do I have to change the perms? maybe 2:4? I say this because this is a 5-node graph.
Plus another Question, Why cant I implement any code i order to manipulate the graphshortestpath to force the code pass by all the nodes. Cannot understand why this is so complicated.
Steven Lord
2018-3-7
If it is a directed graph then you need to use digraph rather than graph. The graph function creates an undirected graph.
As for why it's so complicated, did you read the second link in my answer? The key point from that article: "Both problems [determining whether a graph has a Hamiltonian path or whether it has a Hamiltonian cycle] are NP-complete." The phrase NP-complete is itself a link to another Wikipedia article, whose key paragraph is the following (I added some emphasis on a few key points.)
"Although any given solution to an NP-complete problem can be verified quickly (in polynomial time), there is no known efficient way to locate a solution in the first place; the most notable characteristic of NP-complete problems is that no fast solution to them is known. That is, the time required to solve the problem using any currently known algorithm increases very quickly as the size of the problem grows. As a consequence, determining whether it is possible to solve these problems quickly, called the P versus NP problem, is one of the principal unsolved problems in computer science today."
Note that P versus NP is one of the Millennium Prize problems and is worth US $1 million in prize money if you can solve it.
The question "Is there a Hamiltonian path in my graph?" is simple to ask but not so simple to answer for larger graphs. You want an even harder variant of that, not just looking for a Hamiltonian path but a shortest Hamiltonian path.
For a small graph, use Christine's exhaustive approach. For a larger graph, use Christine's exhaustive approach and wait a while or implement one or more of the algorithms whose papers are linked in the References section on the "Hamiltonian path problem" Wikipedia page.
Jason
2018-3-7
Ok I understand there.
I changed to digraph but the thing is that it doesnot give me the shortest path. Using the bioinfo variants I can check which is the shortest path between specific nodes and thats ok but I want this path to include all nodes. meaning starting from 1 and coming back to it but through the optimal path.
Christine Tobler
2018-3-9
Sorry I just realized I forgot to check up on this post. The shortest path between two nodes will likely not go through all the nodes - so it's a question of where the priority is.
I'm not quite sure what answer you are looking for. Could you tell me in a small example, what answer you are getting, and what answer you are expecting to get?
Jason
2018-3-9
Hi Christine and thank you for your reply. I am looking for a code which does what the bioinfo variants do,namely, finding the optinmal path between two nodes BUT I want to find the this path -for example between node 1 and node2- which passes by ALL the nodes. I am looking for a command, constraint or whatever that can manipulate this piece of code in order to force the path include ALL nodes. Thank you again.
Steven Lord
2018-3-9
We understand what you have asked for. Computing that can be extremely difficult and/or time consuming.
Can you tell us why you want what you have asked for, how you would use it if you were able to compute it? There may be a way to accomplish what you want to do with a different approach or technique, one that avoids the NP-complete problem of finding a Hamiltonian path or cycle.
Jason
2018-3-9
Hi Steven, and thank you for the response. Its part of my diploma thesis . Its similar the TSP but I want to return to the beginning node. I know there is a function for the TSP problem but I dont like the thing that it computes intermediate routes. Whats your opinion on this alternative you are talking about?
Jason
2018-3-9
I know I cannot find the top of the top optimum path but I think I can work this out for lets say 5-7 nodes as an exmaple.
Christine Tobler
2018-3-12
So you are looking for a variant of the code above, but instead of "start at node 1, visit each of nodes 2-5 once, end at node 6" you are looking for "start at node 1, visit each of nodes 2-5 once, end at node 1"? That can easily be achieved with a small change:
W = [3 1 5 4 1 5 4 3 5 4 2 1 3 1 3 3 5 2 4 1];
DG = sparse([1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5],...
[2 3 4 5 1 3 4 5 1 2 4 5 1 2 3 5 1 2 3 4],W);
g = digraph(DG);
% Construct all possible ways that we could traverse all nodes, starting at
% node 1 and ending at node 6:
paths = perms(2:5);
paths = [ones(size(paths, 1), 1) paths];
% Check if a path is feasible (edges exist between all node pairs), and how
% long it is
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
path = paths(ii, :);
edgeID = findedge(g, path(1:end), path([2:end 1]));
if all(edgeID ~= 0)
dist(ii) = sum(g.Edges.Weight(edgeID));
end
end
[~, id] = min(dist)
mypath = paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, mypath([1:end 1]), 'EdgeColor', 'red')
Note this will not work for every possible graph: It's possible that no path that visits all nodes exists (for example if one node has no outgoing / no incoming edges).
Jason
2018-3-12
Thank you very much Christine. So one of the prerequisites to run this code is to have a similar graph as the one on which this certain code is applied.
Plus the answer for the path is completely correct, but I if the id returns the path cost/distance then 15 -in this certain occasion- is wrong. This can be checked through the tables we create in the beginning, so the path distance is 5. And one more question, what happens when I change the perms? If I have a similar graph with 6 or 7 nodes what do I change?
Jason
2018-3-12
and one more -sorry for that-.
Can you please explain what paths = [ones(size(paths, 1), 1) paths]; does?
and what dist = NaN(size(paths, 1), 1); does?
Steven Lord
2018-3-12
id is the index of the minimum distance and the path that achieves that minimum distance, not the minimum distance itself. For the distance itself you'd want dist(id) (or replace the ~ in the min call with a variable in which you want the minimum distance to be stored.)
Let's look at each of the paths and their corresponding distances in tabular form.
pathsAndDistances = table(dist, paths)
Each row of the paths variable in the pathsAndDistances tables contains a 1 followed by a permutation of the vector 2:5. If you had a digraph with 6 or 7 nodes, those rows would each contain a 1 followed by a permutation of the vector 2:6 or 2:7 respectively.
Steven Lord
2018-3-13
The body of the loop isn't very long. Take a look at the documentation for the findedge function. Under what circumstances does it return 0? When it returns something other than 0, what does that return value represent?
Once you know that, under what circumstances would the if statement condition be satisfied?
As for perms, the documentation describes what it does and includes several examples showing what it does.
Jason
2018-3-13
Thanks Steven. I took a look at everything you told me.
When I have a directed graph like this one should I always start from node 1? for example if I want to start from node 2 and finish at node 2 do I have to change the paths=perms( 3:5) ? and something inside the for or maybe ?
Thank you in advance again.
Steven Lord
2018-3-13
Do you want a path or a cycle? If you want a cycle it doesn't really matter where you start. If you want a path and want to start from a different place, permute the numbers of the other nodes then put your starting node at the start of the matrix of permutations.
Jason
2018-3-14
Ok I get it. But the example I am talking about is this one : I got 7 nodes and I want o start from node 1 end at node 7. The path includes 3 of the nodes 2,3,4,5,6 which has the max distance instead of min. I get the previous code and changed it to this
W = [22 30 41 50 52 40 0 60 48 38 44 30 0 80 60 50 75 40 0 60 65 66 68 61 0 71 70 65 44 49 0 50 41 52 55 47 0 0 0 0 0 0];
DG = sparse([1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 7 7 7 7],...
[2 3 4 5 6 7 1 3 4 5 6 7 1 2 4 5 6 7 1 2 3 5 6 7 1 2 3 4 6 7 1 2 3 4 5 7 1 2 3 4 5 6],W);
g = digraph(DG);
% Construct all possible ways that we could traverse all nodes, starting at
% node 1 and ending at node 5 :
paths = combnk(2:6,3);
paths = [ones(size(paths, 1), 1) paths];
% Check if a path is feasible (edges exist between all node pairs), and how
% long it is
dist = NaN(size(paths, 1), 1);
for ii=1:size(paths, 1)
path = paths(ii, :);
edgeID = findedge(g, path(1:end), path([2:end 1]));
if all(edgeID ~= 0)
dist(ii) = sum(g.Edges.Weight(edgeID));
end
end
[shortest_path_distance, id] = min(dist)
mypath = paths(id, :)
p = plot(g, 'EdgeLabel', g.Edges.Weight);
highlight(p, mypath([1:end 7]), 'EdgeColor', 'magenta')
The correct answer for this example is 1->5->3->4->7
But I get something different like 1->4->5->6->1 and the output for the shortest_distance_path is NaN.
Steven Lord
2018-3-19
path(1:end), path([2:end 1])
How many edges does g have that end at node 1 (which is the first column of each row in the paths variable?) You can find this using the predecessors function.
Rather than waiting for us to respond, if your code does something other than what you expect I recommend using the debugging tools to step through the code and make sure it's doing exactly what you think it's doing and what it should be doing.
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!发生错误
由于页面发生更改，无法完成操作。请重新加载页面以查看其更新后的状态。
Translated by 
您也可以从以下列表中选择网站：
如何获得最佳网站性能
选择中国网站（中文或英文）以获得最佳网站性能。其他 MathWorks 国家/地区网站并未针对您所在位置的访问进行优化。
美洲
- América Latina (Español)
- Canada (English)
- United States (English)
欧洲
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom(English)
亚太
- Australia (English)
- India (English)
- New Zealand (English)
- 中国
- 日本Japanese (日本語)
- 한국Korean (한국어)