TSSFL TECHNOLOGY STACK

Posted: **Tue Sep 20, 2016 3:31 pm**

What is the longest path between nodes 1 and 6?

Get glimpse about walks, trails and paths (this will probably help you to understand and answer the question):

The easiest way to solve the graph path problem is to use the Dijkstras Algorithm:

See also:

Posted: **Sat Oct 08, 2016 9:39 pm**

Since a path is a walk such that all vertices and edges (except possibly the first and last vertices - a circle) are distinct, then the longest path from node 1 to node 6 is is given by

$P: [ 1, \ 3, \ 4, \ 5, \ 6]$ , where $1, 3, \hdots, \ 6$ are vertices, as marked by the red color in the diagram below:

Am I wrong? Why is my answer correct or not?

Posted: **Sat Oct 08, 2016 9:49 pm**

What is the longest path between vertices $000$ and $110$ in the graph below?

Posted: **Sun Oct 30, 2016 1:13 am**

Kruskal's Algorithm.
Minimum Spanning Tree algorithm.

For the network above with vertices 1-->6, we can find the Minimum Spanning Tree, means the minimum weights that join two adjacent nodes for the overall network without creating a loop between the nodes.
With small number of nodes, it's possible to create the matrix manually to describe the connection between the nodes. But, with hundreds of nodes in a network then a code must be implemented to find adjacency between the nodes.

Moderators, you may put this code in a good visualization so that 'if', 'end' and those inbuilt statements can be displayed well in colors as in a real editor. Mistakes in the code, corrections and suggestions are appreciated, someone else may write this in C, Java etc.

But, what are the real life examples which uses Kruskal's Algorithm?

MATLAB CODE

Code: [Select all] [Expand/Collapse]

clc;
tic;
minCost=0;
newWeight=0;
index=1;
% The rows of matrix A represent node number (1-->6, col represents weights
% '1' means there is connection between the nodes, '0' vice versa
% so example in column 2,(row1=1,row3=1)means there is connection btn node1
% and node 3 with weight 10;
fprintf('Representation of our network in a Matrix form\n')
A=[     1   1   0   0   0   0   0   0   0   0  
        1   0   1   1   1   0   0   0   0   0
        0   1   1   0   0   1   1   0   0   0
        0   0   0   1   0   1   0   1   0   1
        0   0   0   0   1   0   1   1   1   0
        0   0   0   0   0   0   0   0   1   1
 ]
 
weights=[1  10  1   1   2   5   12  10  2   1];
sW=size(weights);
[nodes sW]=size(A);
newMatrix=zeros(nodes,1);
spanTree=zeros(nodes,1);
for i=1:nodes
    spanTree(i)=i;
end
sizeId=size(spanTree);
for i=1:sW
    [i, indices]=min(weights(:));
    newMatInit=A(:,indices);
   
    verteX=find(newMatInit);
    vert1=spanTree(verteX(1));
    vert2=spanTree(verteX(2));
   if vert1~=vert2
        newMatrix(:,index)=newMatInit;
        minCost=minCost+weights(1,indices);
        newWeight(index)=weights(1,indices);
        index=index+1;
        change=spanTree(verteX(1));
        spanTree(verteX(1))=spanTree(verteX(2));     
        for k=1:sizeId
            status=spanTree(k);
           if status==change
              spanTree(k)=spanTree(verteX(1));
           end
         end
        weights(1,indices)=max(weights);
    else
        weights(1,indices)=max(weights);
    end
end
 [row,col]=find(newMatrix);   % Looking for non-zero elements
 row=row'; 
 newWeight=newWeight';
  a=[];
 for i=1:size(newWeight);
     a(i,:)=row(2*i-1:2*i);    
 end
 fprintf('Computational results for Kruskal algorithm\n')
 fprintf('The final matrix after sorting\n')
 fprintf('Rows represent nodes(1->6) and 1 means connection between nodes\n')
 disp(newMatrix)
 fprintf('The minimum cost for the path:=')
 disp(minCost)
 c=[a newWeight];       % concatenating minimal adjacent nodes and their weights
 fprintf('Connect node1--weight--node2 to get the final minimum tree\n')
 disp('   node1 node2 weight')
 disp(c)
 toc;

OUTPUT

Code: [Select all] [Expand/Collapse]

Representation of our network in a Matrix form
A=   1     1     0     0     0     0     0     0     0     0
     1     0     1     1     1     0     0     0     0     0
     0     1     1     0     0     1     1     0     0     0
     0     0     0     1     0     1     0     1     0     1
     0     0     0     0     1     0     1     1     1     0
     0     0     0     0     0     0     0     0     1     1
 
Computational results for Kruskal algorithm
The final matrix after sorting
Rows represent nodes(1->6) and 1 means connection between nodes
     1     0     0     0     0
     1     1     1     0     1
     0     1     0     0     0
     0     0     1     1     0
     0     0     0     0     1
     0     0     0     1     0
 
The minimum cost for the path:=     6
 
Connect node1--weight--node2 to get the final minimum tree
   node1 node2 weight
     1      2           1
     2      3           1
     2      4           1
     4      6           1
     2      5           2
 
Elapsed time is 0.674206 seconds.

Posted: **Sun Nov 06, 2016 5:58 pm**

Visualization of Kruskal's Algorithm

Credit: http://www.Wikipedia.org

Posted: **Mon Jan 30, 2017 10:54 am**

gaDgeT wrote:Visualization of Kruskal's Algorithm

Credit: http://www.Wikipedia.org

Well animated!

Posted: **Fri Jan 14, 2022 10:35 am**

https://favtutor.com/blogs/dijkstras-algorithm-cpp

TSSFL TECHNOLOGY STACK

Graph Paths

Graph Paths

Graph Paths

Re: Graph Paths

Re: Graph Paths

Re: Graph Paths

Re: Graph Paths

Re: Graph Paths