際際滷

際際滷Share a Scribd company logo

Quantitative methods minimal spanning tree and dijkstra

Download as PPSX, PDF
A
adarsh

The document discusses the minimal spanning tree technique and Dijkstra's algorithm. Minimal spanning tree is used to connect all points in a network with minimum total distance. It takes a fully connected graph with edge distances as input and outputs a tree that connects all nodes with minimum distance. Dijkstra's algorithm finds the shortest paths from a single source node to all other nodes in a graph. It takes a graph with edge costs as input and outputs the lowest cost path between the source and each other node.

1 of 24
MINIMAL- SPANNING TREE Technique to connect all the points of a network while minimizing the distance between them. Input: Fully connected graph with distances known between the nodes. Output: Tree which gives minimum distance that connects all the nodes. BITS Pilani, Pilani Campus
MINIMAL- SPANNING TREE Algorithm: 1. Select any node in the network 2. Connect this node to the nearest node that minimizes total distance. 3. Find and connect the nearest node that is not connected. In case of tie, select arbitrary and proceed. 4. Repeat step 3 until all nodes are connected. BITS Pilani, Pilani Campus
Minimal Spanning Tree- Problem Launderdale Construction Company, Which is currently developing a luxurious housing project in Panama city beach, Florida. Melvin Launderdale, owner and president of Lauderdale Construction, must determine the least expensive way to provide water and power to each house. The network of the House is given in the figure. BITS Pilani, Pilani Campus
Each number depicts- Dist ance in hundreds of feet Problem : 5 4 3 5 7 2 3 7 3 2 3 2 3 8 2 1 1 5 6 6 4 BITS Pilani, Pilani Campus
MINIMAL- SPANNING TREE Solution: 5 4 3 5 7 2 3 7 3 2 3 2 3 8 2 1 1 5 6 6 4 BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Application of Minimal Spanning Tree Network design. Telephone, electrical, hydraulic, TV cable, computer, road Phone network design Problems- Business with several offices , Lease phone lines to connect them up with each other, Phone company charges different amounts of money to connect different pairs of cities. Set of lines that connects all your offices with a minimum total cost. - Spanning tree, since if a network isnt a tree you can always remove some edges and save money BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM A graph search algorithm that solves the single-source shortest path problem. Input: fully connected graph with distances known between the nodes. Output: For a source node in the graph, the algorithm finds the path with lowest cost between that vertex and every other vertex. Can also be used for finding costs of shortest paths from a single vertex to a single destination BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
References 1.) http://optlab- server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo. html 2.) Wikipedia.org 3.) http://www.cs.princeton.edu/~rs/AlgsDS07/14MST.pdf BITS Pilani, Pilani Campus

More Related Content

Quantitative methods minimal spanning tree and dijkstra

  • 1. MINIMAL- SPANNING TREE Technique to connect all the points of a network while minimizing the distance between them. Input: Fully connected graph with distances known between the nodes. Output: Tree which gives minimum distance that connects all the nodes. BITS Pilani, Pilani Campus
  • 2. MINIMAL- SPANNING TREE Algorithm: 1. Select any node in the network 2. Connect this node to the nearest node that minimizes total distance. 3. Find and connect the nearest node that is not connected. In case of tie, select arbitrary and proceed. 4. Repeat step 3 until all nodes are connected. BITS Pilani, Pilani Campus
  • 3. Minimal Spanning Tree- Problem Launderdale Construction Company, Which is currently developing a luxurious housing project in Panama city beach, Florida. Melvin Launderdale, owner and president of Lauderdale Construction, must determine the least expensive way to provide water and power to each house. The network of the House is given in the figure. BITS Pilani, Pilani Campus
  • 4. Each number depicts- Dist ance in hundreds of feet Problem : 5 4 3 5 7 2 3 7 3 2 3 2 3 8 2 1 1 5 6 6 4 BITS Pilani, Pilani Campus
  • 5. MINIMAL- SPANNING TREE Solution: 5 4 3 5 7 2 3 7 3 2 3 2 3 8 2 1 1 5 6 6 4 BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
  • 6. Application of Minimal Spanning Tree Network design. Telephone, electrical, hydraulic, TV cable, computer, road Phone network design Problems- Business with several offices , Lease phone lines to connect them up with each other, Phone company charges different amounts of money to connect different pairs of cities. Set of lines that connects all your offices with a minimum total cost. - Spanning tree, since if a network isnt a tree you can always remove some edges and save money BITS Pilani, Pilani Campus
  • 7. DIJKSTRA ALGORITHM A graph search algorithm that solves the single-source shortest path problem. Input: fully connected graph with distances known between the nodes. Output: For a source node in the graph, the algorithm finds the path with lowest cost between that vertex and every other vertex. Can also be used for finding costs of shortest paths from a single vertex to a single destination BITS Pilani, Pilani Campus
  • 8. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 9. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 10. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 11. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 12. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 13. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 14. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 15. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 16. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 17. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 18. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 19. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 20. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 21. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 22. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 23. DIJKSTRA ALGORITHM BITS Pilani, Pilani Campus
  • 24. References 1.) http://optlab- server.sce.carleton.ca/POAnimations2007/DijkstrasAlgo. html 2.) Wikipedia.org 3.) http://www.cs.princeton.edu/~rs/AlgsDS07/14MST.pdf BITS Pilani, Pilani Campus

Editor's Notes

  1. Animated the example
  2. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  3. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  4. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  5. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  6. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  7. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  8. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  9. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  10. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  11. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)
  12. Bayes theorem is used to accommodate additional data to calculate revised probabilities (posterior probabilities)