›
›

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

pdf 43 trang vanle 2190
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Thuật toán 2 ngăn xếp của Dijkstra", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_thuat_toan_2_ngan_xep_cua_dij.pdf

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

  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