#21 [Lý thuyết đồ thị | Toán rời rạc]. Thuật Toán Dijkstra | Thuật Toán Tìm Đường Đi Ngắn Nhất

Nội dung video hướng dẫn các bạn thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị có trọng số không âm.
Timeline :
00:00 : Mã giả và tư tưởng của Dijkstra
07:10 : Kiểm nghiệm thuật toán Dijkstra
19:40 : Cài đặt thuật toán Dijkstra
31:30 : Xây dựng đường đi ngắn nhất
Mã nguồn tham khảo : ideone.com/Pmj7sa
_____________________________________________
Practice problem :
cses.fi/problemset/task/1671
cses.fi/problemset/task/1195
cses.fi/problemset/task/1196
codeforces.com/problemset/pro...
codeforces.com/problemset/pro...
_____________________________________________
Các series lập trình :
Lập trình C++ : • Ngôn Ngữ Lập trình C++
Lập trình C : • Ngôn Ngữ Lập Trình C
Lý thuyết đồ thị : • Lý Thuyết Đồ Thị | Gra...
Java Collections and Trick : • Java Collections
Trò chuyện với 28tech : • Chia Sẻ Về Ngành Công ...
_____________________________________________
Liên hệ :
►Đăng ký học với mình tại : 28tech.com.vn
►Facebook chia sẻ kiến thức lập trình và thuật toán: / 28techandedu
►Facebook cá nhân : / andrew28042711
►Group : groups/28techgroup/
►Zalo / Phone : [phone]
►Gmail: [e-mail]
© 2022 28tech
#DoThi #28tech #LapTrinh #TDijkstra

[@28tech_]

Thông tin các khóa học mình đang hướng dẫn : 28tech.com.vn/

[@28tech_]

Timeline : 00:00 : Mã giả và tư tưởng của Dijkstra 07:10 : Kiểm nghiệm thuật toán Dijkstra 19:40 : Cài đặt thuật toán Dijkstra 31:30 : Xây dựng đường đi ngắn nhất Mã nguồn tham khảo : ideone.com/Pmj7sa _____________________________________________ Practice problem : cses.fi/problemset/task/1671 cses.fi/problemset/task/1195 cses.fi/problemset/task/1196 codeforces.com/problemset/problem/20/C codeforces.com/problemset/problem/59/E

[@fruith_]

à rồi oke cảm ơn anh ạ

[@nightcoretado3877]

cảm ơn anh

[@lyvc6483]

Cám ơn rất nhiều!

[@28tech_]

OK e nhé

[@user-su9wz4jv3f]

em cảm ơn anh

[@hauthanh1744]

Anh ơi anh làm video hướng dẫn về thuật toán Ford - Bellman đi anh, nó có giống Dijkstra hong anh

[@phanvantai2521]

Em đã hiểu được thuật toán này.Cảm ơn anh

[@28tech_]

Nhớ chia sẻ cho a

[@ongnhat5132]

e học trên lớp ko hiểu gì nhờ a em hiểu đc ròi ạ em cảm ơn a ạ @@28tech_

[@thanhbinhnguyen5943]

Hay quá anh ơi :3

[@28tech_]

🤗🤗🤗🤗

[@nguyenvanhung8560]

thanks a

[@hieuahoang7556]

Ồ đây rồi, cày view thôi

[@28tech_]

🤡🤡🤡 ok e nhé

[@HuySatoou]

Cho mình hỏi sao phần relaxation u=5 d(4) lại giữ nguyên vậy ạ

[@31.nguyentranthangtrung46]

Anh ơi trên lớp cô em kh dạy thuật toán Dijkstra mà dạy thuật toán Floyd, kh biết anh có thể làm về thuật toán Floyd và phân tích về ưu nhược điểm của 2 thuật toán này được kh ạ.

[@maiquochuy1543]

nếu dữ liệu nhỏ thì xài floyd đc còn dữ liệu lớn thì dijks

[@LuuNguyen-kw8mg]

Vậy nếu em muốn in ra k đoạn đường ngắn nhất từ đỉnh s đến đỉnh t thì sao ạ ?

[@puongnguyen4073]

Anh ơi cái điều kiện lúc 23:20 ko có thì có sai khong anh.

[@kienttftu]

Khi đỉnh đã được marked rồi thì ko cần relaxation nữa. Cái việc tính tiếp khoảng cách từ 5 đến 4 và 6 sau khi đỉnh 4 và đỉnh 6 đã marked là không chính xác và không cần thiết!

[@komaiptit5792]

em tuowng cái kc==d[v] r thì cái dk để continue là ntn v ạ

[@vnam3008]

Anh ơi, anh lên video chỉ làm cái code khi mà anh gõ main thì nó ra cả cái khung chương trình luôn đc không anh

[@28tech_]

Nó là snippest nhé em

[@duyvonguyennhat7283]

a làm clip giải bài trên cses đi a

[@28tech_]

bận quá em ạ chưa có thời gian ấy.

[@HGiang-kf4so]

ai giúp mình với, Ct không in đc mảng D, mình không hiểu tại sao #include using namespace std; const int maxn=5001; const long long oo=1e15; typedef pair pm; vector < pair< int, int>>, v[maxn]>; long long l[maxn][2]; long long d[maxn]; priority_queue q; int n, m, k,a,b; long long kq; void docdl() { cin >> n >> m >>k; cin >> a >>b; for (int i=1; i x >> y; d[x]=y; } for (int i=1; i> x >> y >> z; v[x].push_back({y,z}); v[y].push_back({x,z}); } } void dij() { for(int i=1; i

[@bldouyin4145]

Nếu muốn tìm đường đi ngắn nhất mà có trọng số âm thì dùng thuật toán gì ạ > ?

[@PhongNguyen-cc8dd]

bellman-ford

[@lovesegtree]

cho em hỏi làm sao dùng chuột mà vẽ được chữ số đẹp như anh ạ tại em vẽ thấy xấu ghê sợ ko đọc nổi

[@28tech_]

Anh vẽ nhiều nó quen á em ơi.

[@dieudoanvan]

bạn nên để V,E thay vì n,m cách đặt tên biến nên logic tới giải thuật

[@28tech_]

cũng được b :D

[@hoangvietnguyen5788]

anh ơi kênh anh có phần quy hoạch động ko anh có thì cho em xin link với ạ c hoặc c++ nhé a!

[@28tech_]

Không có em ơi, phần này kén người xem lắm

[@hoangvietnguyen5788]

@@28tech_ ok a nhé tại vì cái này khá khó hiểu với bình thg xem a dễ hiểu lắm ạ vì anh kiểu viết ra cái bảng ấy!

[@Lunguyen08]

@@28tech_ làm quy hoạch động đi anh, cấu trúc đề thi hsg ở em nói thẳng ra là 7/20 điểm bài quy hoạch động 😭😭😭

[@minhlequan6482]

Bài này nếu yêu cầu tìm số lượng đường đi ngắn nhất đến 1 đỉnh thì làm thế nào a nhỉ :v

[@toannguyenlekhanh2323]

Đường đi ngắn nhất mà con số lượng à ':))

[@minhlequan6482]

@@toannguyenlekhanh2323 ví dụ có nhiều đường đi cùng tổng trọng số và in ra tất cả các đường đó chẳng hạn. Có bạn nhé

[@huunguyenvonguyen6867]

trên mac có ide c++ nào hỗ trợ bits/stdc++.h> khg anh

[@28tech_]

Có sublime em

[@huunguyenvonguyen6867]

@@28tech_ nó vẫn khg hỗ trợ anh

[@quangninh2204]

a ơi cho e hỏi độ phức tạp thuật toán này là bao nhiêu vậy a

[@28tech_]

Độ phức tạp của thuật toán này nếu em dùng hàng đợi ưu tiên thì là O(ElogV) với E là số cạnh, V là số đỉnh của đồ thị.

[@gaminghardware1471]

Dijkstra phong cách đệ quy void Dijkstra(int s){ if(!visited[s]){ for(auto a:adj[s]){ int v=a.first; int w=a.second; dist[v]=min(dist[v],dist[s]+w); } visited[s]=true; int min_val=INF; int min_cur=0; for(int i=1;idist[i]){ min_val=dist[i]; min_cur=i; } } } if(min_cur==0){ return; } Dijkstra(min_cur); } }

[@KhangNguyen-fg5si]

đồ thị vô hướng thì sao anh ơiii

[@nguyenphuthanhat4530]

Khó hiểu đoạn kc > d[u] quá

[@tuankhanhnguyen1055]

Cho em hỏi là: vì sao phải kc > d[u] vậy ạ. Phải là kc < d[u] chứ ạ do lúc đầu d[u] mình đã set nó bằng INF cho nên nó luôn lớn hơn kc phải không ạ ?? Mong anh hoặc mọi người giải thích ạ

[@28tech_]

Chắc a viết nhầm đó e

[@tuankhanhnguyen1055]

@@28tech_ dạ em cảm ơn anh rất nhiều ạ

[@hoanhoan376]

Vì ban đầu nó luôn > kc nên khi nó < kc tức là nó đã được marked

[@kuetto]

rất là khó hiểu 1 tí 😂

[@vietnguyen2521]

hàm nhập là anh đang biểu diễn đồ thị ở dạng gì vậy ạ

[@28tech_]

Danh sách cạnh nhé em

[@vietnguyen2521]

danh sách cạnh là vector adj mà sao lại thành mảng adj nữa chi vậy ạ mong anh giải thích giúp em

[@Lunguyen08]

@@vietnguyen2521 thì nó là 1 mảng lưu các vector, mỗi phần tử trong vector lại là 1 pair

[@gianglo123]

a vẽ bằng chuột hay bằng bút thế a

[@28tech_]

Chuột nhé em

[@gianglo123]

@@28tech_ vẽ đẹpt thế a

[@oanuc9806]

Anh cho em xin đề bài của bài trên với ạ

[@28tech_]

Em viết lại input là được mà vì lâu anh cũng ko lưu

[@phucanhnguyen5796]

anh cho e hỏi cái vector nó hoạt động như thế nào vậy

[@trongnghiavu9931]

mảng các cặp có kiểu là int int í

[@truongtaman5663]

[@28tech_]

Học dần đi em 😁😁😁😁

[@hoangmai207]

e xin link contest trên hackerrank với ạ

[@28tech_]

Em nhắn tin fb anh để phần mô tả ấy

[@Lunguyen08]

ai giải thích giúp chỗ kc>d[u] được không

[@nguyenthiennhan4376]

bởi vì mỗi đỉnh có thể được tối ưu từ nhiều đỉnh kề khác nhau dẫn đến trong pq có rất nhiều phiên bản của nó. Và vì pq luôn ưu tiên trọng số nhỏ nên về cuối những thằng trọng số to sẽ bị sót lại và ta làm vậy để không phải xét nó khiến mất tg nhé bạn

[@atNguyen-bu6rp]

nếu như này thì số âm vẫn đúng mà nhỉ