Graph Paths

Post Reply
User avatar
Admin
Site Admin
Senior Expert Member
Reactions: 56
Posts: 383
Joined: 10 years ago
Has thanked: 38 times
Been thanked: 32 times
Contact:

#1

What is the longest path between nodes 1 and 6?

Image

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:

0
TSSFL Stack is dedicated to empowering and accelerating teaching and learning, fostering scientific research, and promoting rapid software development and digital technologies
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5223
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#2

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

, where are vertices, as marked by the red color in the diagram below:
Longest-path.png
Am I wrong? Why is my answer correct or not?
0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5223
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#3

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

Image
0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
Joseph Bundala
Expert Member
Reactions: 23
Posts: 55
Joined: 7 years ago
Has thanked: 14 times
Been thanked: 28 times
Contact:

#4

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
  1. clc;
  2. tic;
  3. minCost=0;
  4. newWeight=0;
  5. index=1;
  6. % The rows of matrix A represent node number (1-->6, col represents weights
  7. % '1' means there is connection between the nodes, '0' vice versa
  8. % so example in column 2,(row1=1,row3=1)means there is connection btn node1
  9. % and node 3 with weight 10;
  10. fprintf('Representation of our network in a Matrix form\n')
  11. A=[     1   1   0   0   0   0   0   0   0   0  
  12.         1   0   1   1   1   0   0   0   0   0
  13.         0   1   1   0   0   1   1   0   0   0
  14.         0   0   0   1   0   1   0   1   0   1
  15.         0   0   0   0   1   0   1   1   1   0
  16.         0   0   0   0   0   0   0   0   1   1
  17.  ]
  18.  
  19. weights=[1  10  1   1   2   5   12  10  2   1];
  20. sW=size(weights);
  21. [nodes sW]=size(A);
  22. newMatrix=zeros(nodes,1);
  23. spanTree=zeros(nodes,1);
  24. for i=1:nodes
  25.     spanTree(i)=i;
  26. end
  27. sizeId=size(spanTree);
  28. for i=1:sW
  29.     [i, indices]=min(weights(:));
  30.     newMatInit=A(:,indices);
  31.    
  32.     verteX=find(newMatInit);
  33.     vert1=spanTree(verteX(1));
  34.     vert2=spanTree(verteX(2));
  35.    if vert1~=vert2
  36.         newMatrix(:,index)=newMatInit;
  37.         minCost=minCost+weights(1,indices);
  38.         newWeight(index)=weights(1,indices);
  39.         index=index+1;
  40.         change=spanTree(verteX(1));
  41.         spanTree(verteX(1))=spanTree(verteX(2));    
  42.         for k=1:sizeId
  43.             status=spanTree(k);
  44.            if status==change
  45.               spanTree(k)=spanTree(verteX(1));
  46.            end
  47.          end
  48.         weights(1,indices)=max(weights);
  49.     else
  50.         weights(1,indices)=max(weights);
  51.     end
  52. end
  53.  [row,col]=find(newMatrix);   % Looking for non-zero elements
  54.  row=row';
  55.  newWeight=newWeight';
  56.   a=[];
  57.  for i=1:size(newWeight);
  58.      a(i,:)=row(2*i-1:2*i);    
  59.  end
  60.  fprintf('Computational results for Kruskal algorithm\n')
  61.  fprintf('The final matrix after sorting\n')
  62.  fprintf('Rows represent nodes(1->6) and 1 means connection between nodes\n')
  63.  disp(newMatrix)
  64.  fprintf('The minimum cost for the path:=')
  65.  disp(minCost)
  66.  c=[a newWeight];       % concatenating minimal adjacent nodes and their weights
  67.  fprintf('Connect node1--weight--node2 to get the final minimum tree\n')
  68.  disp('   node1 node2 weight')
  69.  disp(c)
  70.  toc;

OUTPUT
  1. Representation of our network in a Matrix form
  2. A=   1     1     0     0     0     0     0     0     0     0
  3.      1     0     1     1     1     0     0     0     0     0
  4.      0     1     1     0     0     1     1     0     0     0
  5.      0     0     0     1     0     1     0     1     0     1
  6.      0     0     0     0     1     0     1     1     1     0
  7.      0     0     0     0     0     0     0     0     1     1
  8.  
  9. Computational results for Kruskal algorithm
  10. The final matrix after sorting
  11. Rows represent nodes(1->6) and 1 means connection between nodes
  12.      1     0     0     0     0
  13.      1     1     1     0     1
  14.      0     1     0     0     0
  15.      0     0     1     1     0
  16.      0     0     0     0     1
  17.      0     0     0     1     0
  18.  
  19. The minimum cost for the path:=     6
  20.  
  21. Connect node1--weight--node2 to get the final minimum tree
  22.    node1 node2 weight
  23.      1      2           1
  24.      2      3           1
  25.      2      4           1
  26.      4      6           1
  27.      2      5           2
  28.  
  29. Elapsed time is 0.674206 seconds.

0
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5223
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#5

Visualization of Kruskal's Algorithm

Image

Credit: http://www.Wikipedia.org
0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
User avatar
Admin
Site Admin
Senior Expert Member
Reactions: 56
Posts: 383
Joined: 10 years ago
Has thanked: 38 times
Been thanked: 32 times
Contact:

#6

gaDgeT wrote:Visualization of Kruskal's Algorithm

Image

Credit: http://www.Wikipedia.org
Well animated!
0
TSSFL Stack is dedicated to empowering and accelerating teaching and learning, fostering scientific research, and promoting rapid software development and digital technologies
User avatar
Eli
Senior Expert Member
Reactions: 183
Posts: 5223
Joined: 9 years ago
Location: Tanzania
Has thanked: 75 times
Been thanked: 88 times
Contact:

#7

0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
Post Reply

Return to “Graph Theory”

  • Information
  • Who is online

    Users browsing this forum: No registered users and 0 guests