dijkstra algorithm function problem

the function is defined but I can't understand the problem

Answer 1

[yusuf]

[Walter Roberson]

In your line

function [araba] = dijkstra1(G,1,7)

what is MATLAB supposed to do with the 1 and the 7? Is there some matching key telling MATLAB that inside the function, you can get to the 7 by naming a particular variable? It looks like you probably intend one to be a start node and the other to be an end node, but how is the function body supposed to know which is which and how is the function body to know how to refer to the values?

For example if the first thing in your function was intended to be something like testing whether G has at least as many rows and columns as the maximum of the start and end nodes, then you would not be able to code something like

maxnode = max(startnode, endnode);
if min(size(G)) < maxnode; error('G too small'); end

because startnode and endnode would be undefined.

[yusuf]

Thank you very much for your reply. I just wanted to test the example written in the function of the algorithm. I got an error even though I did exactly the same

Answer 2

[Torsten]

Works for me.

%---------------------------------------------------
% Dijkstra Algorithm
% author : Dimas Aryo
% email : [e-mail]
%
% usage
% [cost rute] = dijkstra(Graph, source, destination)
% 
% example
G = [0 3 9 0 0 0 0;
    0 0 0 7 1 0 0;
    0 2 0 7 0 0 0;
    0 0 0 0 0 2 8;
    0 0 4 5 0 9 0;
    0 0 0 0 0 0 4;
    0 0 0 0 0 0 0;
    ];
plot(digraph(G))

[e L] = dijkstra(G,1,7)

e = 15

L = 1×6

7 6 4 5 2 1

%---------------------------------------------------
function [e L] = dijkstra(A,s,d)

if s==d
    e=0;
    L=[s];
else
    
    A = setupgraph(A,inf,1);
    
    if d==1
        d=s;
    end
    A=exchangenode(A,1,s);
    
    lengthA=size(A,1);
    W=zeros(lengthA);
    for i=2 : lengthA
        W(1,i)=i;
        W(2,i)=A(1,i);
    end
    
    for i=1 : lengthA
        D(i,1)=A(1,i);
        D(i,2)=i;
    end
    
    D2=D(2:length(D),:);
    L=2;
    while L<=(size(W,1)-1)
        L=L+1;
        D2=sortrows(D2,1);
        k=D2(1,2);
        W(L,1)=k;
        D2(1,:)=[];
        for i=1 : size(D2,1)
            if D(D2(i,2),1)>(D(k,1)+A(k,D2(i,2)))
                D(D2(i,2),1) = D(k,1)+A(k,D2(i,2));
                D2(i,1) = D(D2(i,2),1);
            end
        end
        
        for i=2 : length(A)
            W(L,i)=D(i,1);
        end
    end
    if d==s
        L=[1];
    else
        L=[d];
    end
    e=W(size(W,1),d);
    L = listdijkstra(L,W,s,d);
end
end
    function G = exchangenode(G,a,b)
        
        %Exchange element at column a with element at column b;
        buffer=G(:,a);
        G(:,a)=G(:,b);
        G(:,b)=buffer;
        
        %Exchange element at row a with element at row b;
        buffer=G(a,:);
        G(a,:)=G(b,:);
        G(b,:)=buffer;
        
    end
    function L = listdijkstra(L,W,s,d)
        
        index=size(W,1);
        while index>0
            if W(2,d)==W(size(W,1),d)
                L=[L s];
                index=0;
            else
                index2=size(W,1);
                while index2>0
                    if W(index2,d)<W(index2-1,d)
                        L=[L W(index2,1)];
                        L=listdijkstra(L,W,s,W(index2,1));
                        index2=0;
                    else
                        index2=index2-1;
                    end
                    index=0;
                end
            end
        end
    end
    function G = setupgraph(G,b,s)
        
        if s==1
            for i=1 : size(G,1)
                for j=1 :size(G,1)
                    if G(i,j)==0
                        G(i,j)=b;
                    end
                end
            end
        end
        if s==2
            for i=1 : size(G,1)
                for j=1 : size(G,1)
                    if G(i,j)==b
                        G(i,j)=0;
                    end
                end
            end
        end
    end

[yusuf]

where am i doing wrong. I can not understand

[Torsten]

If you copy the code from above into your local MATLAB, does it work properly ?

[yusuf]

it didn't work in the program on my own computer. but it worked in the online program. I have a question, what does the resource value we entered mean? so the value 1 is the number 1 in the matrix

[Torsten]

From the example documentation:

Finding shortest path form node 1 to node 7.

Which MATLAB version do you use ? What error message do you get if you run the above code on your computer ?

[yusuf]

path has "6" but matrix doesn't have "6"

[yusuf]

so the app doesn't do the job i specify?

[Torsten]

L gives the nodes, not the weights.

[yusuf]

Is there an algorithm that can do the job I mentioned in the picture?

[Torsten]

And what is the "job" in plain words ?

[yusuf]

I marked it in red in the picture I posted. shortest path between two points in the matrix

[Torsten]

Between which nodes ?

I included the corresponding digraph of G above.

[yusuf]

For example, between the point (2,3) and point (5,4) in the matrix

[Torsten]

I think you should read what the matrix G represents.

There is no "point" (2,3) or "point" (5,4), there are only nodes 1,2,...,7.

If you refer to (2,3) and (5,4), you refer to the directed edges of the graph.

[yusuf]

What is a node? are the columns

[yusuf]

Could you please show me the knots with a picture?

[Torsten]

The number of rows (or columns) of G is the number of nodes.

These nodes are partially connected by edges. If G(i,j) = 0, there is no connection from node i to node j. If there is an entry G(i,j) > 0, node j can be accessed from node i with cost G(i,j).

The example for the code asks to find a path (sequence of edges) from node 1 to node 7 that minimizes the sum of the costs.

[yusuf]

i can't understand this path has "6" but matrix doesn't have "6"

[Torsten]

6 is the node number "6". The numbers in the matrix are not node numbers, but costs to reach node i from node j, e.g. G(4,7) = 8 means: there is a street between node 4 to node 7 and it costs 8 dollars to use this street.

Look at the digraph I plotted from the matrix G above. Maybe you understand better then.

[yusuf]

I'm so sorry for taking your time. Our teacher gave us an assignment. It's a traveling salesman problem, but we need to do it inside the matrix. For example, the process of finding the shortest path between the points (4,7) and (8,6) completely fitting in any matrix. Is there an algorithm that can do this

[Torsten]

Sorry, but if you refuse to learn what the matrix G represents, I cannot help you further.

The elements of the matrix G are no "points" (at least in this case - I don't know whether the matrix your teacher gave you are some spatial coordinates that might indicate points in space).

The element G(i,j) in the matrix G here are costs to reach point j from point i.

E.g. in the example given you go from point 1 to point 2. This costs G(1,2) = 3 dollars.

Then from point 2 you go to point 5. This costs G(2,5) = 1 dollar.

Then from point 5 you go to point 4. This costs G(5,4) = 5 dollars.

Then from point 4 you go to point 6. This costs G(4,6) = 2 dollars.

Then from point 6 you go to point 7. This costs G(6,7) = 4 dollars.

Thus your way is

L = 1 -> 2 -> 5 -> 4 -> 6 -> 7

and this way costs

3 + 1 + 5 + 2 + 4 = 15 dollars.

The travelling salesman problem is harder than the one here you can use Dijkstra for. So the code you found is not suited to solve the travelling salesman problem. But the matrix G for the travelling salesman problem is usually made up the in the same way as the matrix G here. So it won't be a waste of time to study the simple Dijkstra code first.

[yusuf]

Is the path it follows here the lowest cost?

[Torsten]

The graph shows the connections of the nodes specified in the matrix G.

If you want, try to mark the optimal path 1 -> 2 -> 5 -> 4 -> 6 -> 7 in red.

[yusuf]

I don't understand unfortunately. Is there a video that explains this in the simplest way?

[Walter Roberson]

Yes, if you search YouTube for "traveling salesman problem" and watch all of the thousands of videos, then at the end you would have found that one of them would appear to be the simplest explanation to you. We cannot predict which of them it would be, as we would almost certainly find different videos to have the simplest explanation for us.

[Walter Roberson]

No the path followed in that diagram is not the lowest cost for Traveling Salesman.

Traveling Salesman needs to return to its origin. But look at node 7 and see that it has two arrows leading to it but no arrows leaving. So once you reach node 7 you can check out any time you like but you can never leave, so you can never return to the origin.

[yusuf]

so is there any place where you can help me with my problem?

[Torsten]

You did not yet state your problem.

[yusuf]

I'm so sorry for taking your time. Our teacher gave us an assignment. It's a traveling salesman problem, but we need to do it inside the matrix. For example, the process of finding the shortest path between the points (4,7) and (8,6) completely fitting in any matrix. Is there an algorithm that can do this

[Walter Roberson]

What you have is a distance matrix. Santhanakrishnan Narayanan has a File Exchange Contribution that works from distance matrices.

[Torsten]

And how do you measure the distance between points in the matrix ?

What are the elements of the matrix and what do they mean ?

Finding a shortest path between two points is not the travelling salesman problem.

[Walter Roberson]

Perhaps you are expecting something like the "cost_path" I added here.

Cost paths are ambiguous. You might be able to follow them to a point, but then you find a node in which there are two or more possible routes with the same cost, and at that point you can only figure out which of the routes was taken by looking further into the route and matching against the available costs, hypothesizing that perhaps you took at particular route until you either reach the goal or encounter a situation in which the hypothesis can no longer be continued. It is much better to have the node route list.

This might answer your question about using this Dijkstra code, but as Torsten points out, Traveling Salesman Problem is a different problem that cannot be solved by Dijkstra Algorithm.

%---------------------------------------------------
% Dijkstra Algorithm
% author : Dimas Aryo
% email : [e-mail]
%
% usage
% [cost rute] = dijkstra(Graph, source, destination)
% 
% example
G = [0 3 9 0 0 0 0;
    0 0 0 7 1 0 0;
    0 2 0 7 0 0 0;
    0 0 0 0 0 2 8;
    0 0 4 5 0 9 0;
    0 0 0 0 0 0 4;
    0 0 0 0 0 0 0;
    ];
plot(digraph(G))

[e, L] = dijkstra(G,1,7)

e = 15

L = 1×6

7 6 4 5 2 1

visited_in_order = fliplr(L)

visited_in_order = 1×6

1 2 5 4 6 7

cost_path = G(sub2ind(size(G), visited_in_order(1:end-1), visited_in_order(2:end)))

cost_path = 1×5

3 1 5 2 4

%---------------------------------------------------
function [e L] = dijkstra(A,s,d)

if s==d
    e=0;
    L=[s];
else
    
    A = setupgraph(A,inf,1);
    
    if d==1
        d=s;
    end
    A=exchangenode(A,1,s);
    
    lengthA=size(A,1);
    W=zeros(lengthA);
    for i=2 : lengthA
        W(1,i)=i;
        W(2,i)=A(1,i);
    end
    
    for i=1 : lengthA
        D(i,1)=A(1,i);
        D(i,2)=i;
    end
    
    D2=D(2:length(D),:);
    L=2;
    while L<=(size(W,1)-1)
        L=L+1;
        D2=sortrows(D2,1);
        k=D2(1,2);
        W(L,1)=k;
        D2(1,:)=[];
        for i=1 : size(D2,1)
            if D(D2(i,2),1)>(D(k,1)+A(k,D2(i,2)))
                D(D2(i,2),1) = D(k,1)+A(k,D2(i,2));
                D2(i,1) = D(D2(i,2),1);
            end
        end
        
        for i=2 : length(A)
            W(L,i)=D(i,1);
        end
    end
    if d==s
        L=[1];
    else
        L=[d];
    end
    e=W(size(W,1),d);
    L = listdijkstra(L,W,s,d);
end
end
    function G = exchangenode(G,a,b)
        
        %Exchange element at column a with element at column b;
        buffer=G(:,a);
        G(:,a)=G(:,b);
        G(:,b)=buffer;
        
        %Exchange element at row a with element at row b;
        buffer=G(a,:);
        G(a,:)=G(b,:);
        G(b,:)=buffer;
        
    end
    function L = listdijkstra(L,W,s,d)
        
        index=size(W,1);
        while index>0
            if W(2,d)==W(size(W,1),d)
                L=[L s];
                index=0;
            else
                index2=size(W,1);
                while index2>0
                    if W(index2,d)<W(index2-1,d)
                        L=[L W(index2,1)];
                        L=listdijkstra(L,W,s,W(index2,1));
                        index2=0;
                    else
                        index2=index2-1;
                    end
                    index=0;
                end
            end
        end
    end
    function G = setupgraph(G,b,s)
        
        if s==1
            for i=1 : size(G,1)
                for j=1 :size(G,1)
                    if G(i,j)==0
                        G(i,j)=b;
                    end
                end
            end
        end
        if s==2
            for i=1 : size(G,1)
                for j=1 : size(G,1)
                    if G(i,j)==b
                        G(i,j)=0;
                    end
                end
            end
        end
    end

Answer 3

[Walter Roberson]

Suppose you have an N x 2 cell array P, with a row P(K,:) representing information about a potential path to take. P{K,1} is the total cost encountered so far in the K'th proposed route, and P{K,2} is a list of nodes that have been visited already.

Initialize P{1,1} = 0 (you got to the starting node for free) and P{1,2} = starting node -- because traveling salesman must visited every node, this might as well be the first node.

At any time:

1. Extract the first row in P into separate variables, such as a current cost and a current route
2. delete the first row from P
3. if the current route includes all of the nodes ending back at the original location, then save the current cost and the current route as one of the Traveling Salesmen paths. (If you want, you could prune it immediately if the cost is greater than the cost associated with the best path you have found so far.) In this case, after recording the path (or throwing it away), there is no need to queue any further possible steps for this path since you already got t
4. examine the cost matrix G row associated with the node given by the last entry in the current route
5. for each non-zero cost you find there, determine whether the target node (column number) already appears in the current route. If so then move on to the next non-zero entry -- with the exception that if the target node is the start node and you have visited all of the other nodes, then this is a solution and you should queue it as described in the next step
6. for each entry that was not already in the current route, add a new row to P, with the cost being the current cost plus the value from the cost matrix for that row and column, and with the route being the current route followed by the node number of the target (the column number).
7. By now you have removed this potential path and replaced it (end of P) with all possible cases of taking one further step after that potential path.
8. If there were no non-zero entries that lead to places you have not already visited, then you reached a dead end and the potential path does not need to be considered further. Which you do not need to do anything special for, as it just means that you did not queue any further potential paths from here. At any given time, P contains only paths that have worked so far, as far as they have gone
9. loop back to step 1 if P is not empty
10. you now have either saved all possible solutions, or at least the ones that are lowest cost. Output them.

[yusuf]

the operations you mentioned are valid only on the distance matrix, right?

[Walter Roberson]

Do you have some other kind of matrix that you need the code to work with?