Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Thuật toán 2 ngăn xếp của Dijkstra - Đào Nam Anh

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 3: Thuật toán 2 ngăn xếp của Dijkstra - Đào Nam Anh

1. • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applyingDATA that operator STRUCTURE to those values onto AND the operand ALGORITHM stack. Dijkstra’s Stack • Left parenthesis: ignore. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Thuật toán 2 ngăn xếp của Dijkstra value stackDr. Dao Namoperator Anh stack Data Structure and Algorithm 1
2. Resource - Reference • Value: push onto the value stack. • Operator:Slides ofpush Robert onto the Sedgewick operator stack., and Kevin Wayne, • Rightedit parenthesis: by Dao Nam pop operatorAnh. Major and two Reference: values; push the result of applying• Robert that operator Sedgewick to those ,values and Kevin onto the Wayne, operand “Algorithms”stack. • Left parenthesis:Princeton University,ignore. 2011, Addison Wesley • Algorithm in C (Parts 1-5 Bundle)- Third Edition by Robert Sedgewick, Addison-Wesley value stack operator stack Data Structure and Algorithm 2
3. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. infix expression value stack operator stack (fully parenthesized) ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) operand Data Structureoperator and Algorithm 3
4. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 4
5. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 5
6. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 1 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 6
7. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 1 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 7
8. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 8
9. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 9
10. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 10
11. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 11
12. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 2 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 12
13. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 2 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 13
14. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 2 + 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 14
15. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 2 + 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 15
16. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 3 2 + 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 16
17. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 3 2 + 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 17
18. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 3 + 2 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 18
19. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 3 + 2 = 5 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 19
20. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 20
21. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 21
22. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 22
23. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 23
24. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 24
25. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 4 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 25
26. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 4 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 26
27. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 4 * 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 27
28. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 4 * 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 28
29. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 4 * 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 29
30. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 4 * 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 30
31. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 * 4 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 31
32. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 5 * 4 = 20 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 32
33. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 20 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 33
34. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 20 5 * 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 34
35. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 20 * 5 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 35
36. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 20 * 5 = 100 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 36
37. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 100 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 37
38. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 100 1 + value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 38
39. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 100 + 1 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 39
40. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 100 + 1 = 101 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 40
41. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 101 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 41
42. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. 101 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 42
43. Thuật toán 2 ngăn xếp của Dijkstra • Value: push onto the value stack. • Operator: push onto the operator stack. • Right parenthesis: pop operator and two values; push the result of applying that operator to those values onto the operand stack. • Left parenthesis: ignore. result 101 value stack operator stack ( 1 + ( ( 2 + 3 ) * ( 4 * 5 ) ) ) Data Structure and Algorithm 43