Struktur Diskret : Permasalahan Jarak Terdekat ( Shortest Circuit )
Shortest Path Problems
Weighted Graphs
Graphs that have a number assigned to each edge are called weighted graphs. Problems which modeled using weighted graphs
- Airline system (vertices: cities, edges: flight distances/ times/fares)
- Computer network (vertices: computers, edges: communication costs/response times/ distances)
Types of problems need to solve :
Shortest path/ path of least length :
Smallest flight time, cheapest fare, fastest response time, shortest distance.
A circuit with shortest total length that visits every vertex of a complete graph exactly once :
Traveling salesman problem.
Shortest-Path Algorithm
Brute Force
What is the length of a shortest path between a to z in the given weighted graph ?
We will solve this problem by finding the length of a shortest path from a to successive vertices, until z is reach.
How ?
- List all the possible path with its length
- a – b – c – z ( length: 9 )
- a – b – e – z ( length: 8 )
- a – d – e – z ( length: 6 )
- a – d – e – b – c – z ( length: 13 )
- Chose a path with the shortest length
- a – d – e – z ( length: 6 )
Dijkstra’s Algorithm
Let's call the node we are starting with an initial node. Let a distance of a node Y be the distance from the initial node to it. Dijkstra's algorithm will assign some initial distance values and will try to improve them step-by-step.
- Assign to every node a distance value. Set it to zero for our initial node and to infinity for all other nodes.
- Mark all nodes as unvisited. Set initial node as current.
- For current node, consider all its unvisited neighbors and calculate their distance (from the initial node). For example, if current node (A) has distance of 6, and an edge connecting it with another node (B) is 2, the distance to B through A will be 6+2=8. If this distance is less than the previously recorded distance (infinity in the beginning, zero for the initial node), overwrite the distance.
- When we are done considering all neighbors of the current node, mark it as visited (use circle). A visited node will not be checked ever again; its distance recorded now is final and minimal.
- Set the unvisited node with the smallest distance (from the initial node) as the next "current node" and continue from step 3.
Example 1: Dijkstra’s Algorithm
Use Dijkstra’s Algorithm to find the length of a shortest path between a to z in the given weighted graph.
Solution :
The algorithm terminate when z is circled. A shortest path from a to z is a, c, b, d, e, z with length 13.
Example 2: Dijkstra’s Algorithm
Use Dijkstra’s Algorithm to find the length of a shortest path between a to z in the given weighted graph.
Solution (by table) :
Travelling Salesman Problems ( TSP )
The traveling salesperson problem asks for the circuit of minimum total weight in a weighted, complete, undirected graph that visits each vertex exactly once and returns to its starting point. This equivalent to asking for a Hamilton circuit with minimum total weight in the complete graph, because each vertex is visited exactly once in the circuit.
Sumber
Slide Strukdis : Shortest Path
Posting Komentar