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
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 ạ.
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
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!
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 ạ
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
![#22 [Lý thuyết đồ thị | Toán rời rạc]. Chu Trình Euler Và Đường Đi Euler](http://i.ytimg.com/vi/RauZYMePmRg/mqdefault.jpg)
![#22 [Lý thuyết đồ thị | Toán rời rạc]. Chu Trình Euler Và Đường Đi Euler](/img/tr.png)
![#18 [Lý thuyết đồ thị]. Cài đặt Thuật Toán PRIM Tìm Cây Khung Cực Tiểu | Cây Khung Nhỏ Nhất](http://i.ytimg.com/vi/Nu0Dsi5LwFI/mqdefault.jpg)
![#20 [Lý thuyết đồ thị | Toán rời rạc]. Kiểm Tra Đỉnh Trụ ( Khớp) Và Cạnh Cầu | Khớp Và Cầu](/img/n.gif)
Thông tin các khóa học mình đang hướng dẫn : 28tech.com.vn/
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
Em đã hiểu được thuật toán này.Cảm ơn anh
Nhớ chia sẻ cho a
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_
hay quá!!!!!!!!!!!!!!!
hay quá a oiw >
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
Anh ơi cái điều kiện lúc 23:20 ko có thì có sai khong anh.
Hay rùi A ơi
Cám ơn rất nhiều!
OK e nhé
Hay quá anh ơi :3
🤗🤗🤗🤗
Ồ đây rồi, cày view thôi
🤡🤡🤡 ok e nhé
Cho mình hỏi sao phần relaxation u=5 d(4) lại giữ nguyên vậy ạ
à rồi oke cảm ơn anh ạ
cảm ơn anh
em cảm ơn anh
trên mac có ide c++ nào hỗ trợ bits/stdc++.h> khg anh
Có sublime em
@@28tech_ nó vẫn khg hỗ trợ anh
em tuowng cái kc==d[v] r thì cái dk để continue là ntn v ạ
đồ thị vô hướng thì sao anh ơiii
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
Anh vẽ nhiều nó quen á em ơi.
ah có bài thuật toán Froyd không ah?
Chưa có em ạ
Anh cho em xin đề bài của bài trên với ạ
Em viết lại input là được mà vì lâu anh cũng ko lưu
cam on sep!
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 ạ ?
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 ạ.
nếu dữ liệu nhỏ thì xài floyd đc còn dữ liệu lớn thì dijks
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ì ạ > ?
bellman-ford
hàm nhập là anh đang biểu diễn đồ thị ở dạng gì vậy ạ
Danh sách cạnh nhé em
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
@@vietnguyen2521 thì nó là 1 mảng lưu các vector, mỗi phần tử trong vector lại là 1 pair
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
Đường đi ngắn nhất mà con số lượng à ':))
@@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é
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
a làm clip giải bài trên cses đi a
bận quá em ạ chưa có thời gian ấy.
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
cũng được b :D
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
Nó là snippest nhé em
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!
Không có em ơi, phần này kén người xem lắm
@@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!
@@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 😭😭😭
a vẽ bằng chuột hay bằng bút thế a
Chuột nhé em
@@28tech_ vẽ đẹpt thế a
a ơi cho e hỏi độ phức tạp thuật toán này là bao nhiêu vậy a
Độ 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ị.
thanks a
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!
anh cho e hỏi cái vector nó hoạt động như thế nào vậy
mảng các cặp có kiểu là int int í
Khó hiểu đoạn kc > d[u] quá
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);
}
}
e xin link contest trên hackerrank với ạ
Em nhắn tin fb anh để phần mô tả ấy
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 ạ
Chắc a viết nhầm đó e
@@28tech_ dạ em cảm ơn anh rất nhiều ạ
Vì ban đầu nó luôn > kc nên khi nó < kc tức là nó đã được marked
rất là khó hiểu 1 tí 😂
ai giải thích giúp chỗ kc>d[u] được không
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
Học dần đi em 😁😁😁😁
nếu như này thì số âm vẫn đúng mà nhỉ