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 1 day ago All in One: YouTube, TED, X, Facebook and Instagram Reels, Videos, Images and Text Posts View the latest post Replies 332 Views 40334
- by Eli 1 day ago Iran's President Ebrahim Raisi Aged 63 Dies in a Helicopter Crash View the latest post Replies 3 Views 63
- by Eli 1 day ago Re: What is in Your Mind? View the latest post Replies 717 Views 307071
- by Eli 3 days ago PySpark for Large Data Processing View the latest post Replies 2 Views 8170
- by Eli 3 days ago Online Bible View the latest post Replies 3 Views 23330
- by Eli 3 days ago Generating SSH Key and Adding it to the ssh-agent for Authentication on GitHub View the latest post Replies 1 Views 487
- by Eli 1 week ago Russia Invades Ukraine View the latest post Replies 663 Views 240894
- by Eli 2 weeks ago President Museveni's Speech During International Development Association (IDA) Summit View the latest post Replies 1 Views 509
- by Eli 2 weeks ago From Simple Linear Regression Analysis to Covariance & Correlation to Independent Determinant, and R-Squared View the latest post Replies 11 Views 25143
- by Eli 2 weeks ago Collection of Greatest Christian Hymns of all Times View the latest post Replies 34 Views 72494
-
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: 183
- Posts: 5410
- 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