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

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?

[Matt J]

What should I do to go to node 3 through visited node 4?

Why do you need to? Why not just stop at node 6? Is the objective to visit every node?

[Michal Zimnicki]

Exactly. Objective is to visit every node.

[Matt J]

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.

Answer 1

[John D'Errico]

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.