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:
-
- Active Topics
-
-
- by Eli 23 hours ago Shared Images View the latest post Replies 6 Views 1467
- by Eli 2 days ago Re: What is in Your Mind? View the latest post Replies 728 Views 323755
- by Eli 3 days ago Dr Wahome: How World Health Organization (WHO) is Doing Bad Things View the latest post Replies 1 Views 74
- by Eli 4 days ago Introduction to Abstract Algebra View the latest post Replies 4 Views 11001
- by Eli 5 days ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 333 Views 50872
- by Eli 5 days ago Generating SSH Key and Adding it to the ssh-agent for Authentication on GitHub View the latest post Replies 2 Views 1162
- by Eli 1 week ago Russia Invades Ukraine View the latest post Replies 668 Views 257183
- by Eli 1 week ago How AI Could Empower any Business View the latest post Replies 1 Views 303
- by Eli 1 week ago Pondering Big Cosmology Questions Through Lectures and Dialogues View the latest post Replies 35 Views 62176
- by Eli 1 week ago The U.S - China Rivalry, Taiwan and Hong Kong View the latest post Replies 1 Views 415
-
Graph Paths
- Admin
- Site Admin
- Senior Expert Member
- Reactions: 56
- Posts: 383
- Joined: 10 years ago
- Has thanked: 38 times
- Been thanked: 32 times
- Contact:
0
TSSFL Stack is dedicated to empowering and accelerating teaching and learning, fostering scientific research, and promoting rapid software development and digital technologies
- Eli
- Senior Expert Member
- Reactions: 185
- Posts: 5450
- Joined: 9 years ago
- Location: Tanzania
- Has thanked: 75 times
- Been thanked: 88 times
- Contact:
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:
Am I wrong? Why is my answer correct or not?
, where are vertices, as marked by the red color in the diagram below:
Am I wrong? Why is my answer correct or not?
0
TSSFL -- A Creative Journey Towards Infinite Possibilities!
-
- Expert Member
- Reactions: 23
- Posts: 55
- Joined: 7 years ago
- Has thanked: 14 times
- Been thanked: 28 times
- Contact:
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
OUTPUT
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
- 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;
- 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.
0
- Admin
- Site Admin
- Senior Expert Member
- Reactions: 56
- Posts: 383
- Joined: 10 years ago
- Has thanked: 38 times
- Been thanked: 32 times
- Contact:
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
-
- Information
-
Who is online
Users browsing this forum: No registered users and 0 guests