Going back to unvisited node through visited node by minimum weight of edge

1 次查看（过去 30 天）
Michal Zimnicki
Michal Zimnicki 2023-2-25
评论： Matt J 2023-2-25
I made a list of unvisited nodes, edges and visited nodes. Starting node is 4 and algoritm chooses edge by its minimum weight, so the next node is 6. I have two problems:
  1. How can I avoid looping edges from node 4 to 6 and vice versa?
  2. What should I do to go to node 3 through visited node 4?
  3 个评论
显示 1更早的评论
Matt J
Matt J 2023-2-25
Well, in the graph you've shown, there are no paths that visit all nodes only once. So, the objective is not achievable. Perhaps you should describe your ulterior motives more fully, so that a better objective can be discussed.

请先登录，再进行评论。

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

采纳的回答

John D'Errico
John D'Errico 2023-2-25
编辑：John D'Errico 2023-2-25
Ran in:
Why are you not using the existing graph tools to solve graph problems? It is never a good idea to write your own code to solve problems that are best solved using code written by professionals.
But if you insist on writing the code (which suggests this is homework) then there are simple ways to resolve this problem. Once you have traveled along an edge, then mark that edge as no longer able to be traversed. (Or, if you prefer, delete it from the list of edges, but that will make for slower code, if you are actually storing a list of edges.) The edge connecting nodes 4 and 6 should appear as TWO edges, so the edge 4-->6 and the edge 6-->4.
One simple way to effectively mark an edge as no longer traversable, is to reset the cost for traversing the edge in that direction as inf, or if zero indicates that for you, then set the cost for that edge to zero to effectively delete it.) Note that if you are using a matrix to store the edge costs, perhaps like this:
G = [0 1 2 0 0 0;
1 0 0 0 6 0;
2 0 0 3 4 0;
0 0 3 0 5 1;
0 6 4 5 0 0;
0 0 0 1 0 0];
plot(graph(G))
Note that the matrix storing the edges for this graph is initially symmetric. That tells us the cost for traversing the edge 4-->6 is the same as traversing the edge 6-->4. Both costs are initially 1. We can see that, because
G(4,6)
ans = 1
G(6,4)
ans = 1
But after traversing an edge, you can always reset the cost along that edge in one direction to indicate it is no longer traversable in that direction.
And finally, if you do start playing around with the costs along edges, do so in a COPY of the array where you will store the graph.

更多回答（0 个）

类别

在 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