[Toán RR] giải hộ mình câu này

[11520218]

Dùng thuật toán Dijkstra tìm đường đi ngắn nhất từ đỉnh a đến đỉnh z và chiều dài của nó trong đồ thị vô hướng có trọng lượng sau:

Untitled.jpg

mấy bạn pro giải dùm mình phát, cám ơn nhiều:beauty:

[12520795]

Em có làm thử bài của anh, hy vọng đúng :love: mà cái này là làm theo dijkstra của MMT nhaz anh, cũng dùng đc trong môn CTRR đó
Dijkstra.jpg

[11520218]

Em có làm thử bài của anh, hy vọng đúng :love: mà cái này là làm theo dijkstra của MMT nhaz anh, cũng dùng đc trong môn CTRR đó
[ATTACH=CONFIG]11387[/ATTACH]

Dijkstra của toán RR thầy Tình trình bày khác, của bạn khó nhìn quá :surrender:

[12520222]

1.jpg10 kí tự chưa?

[11520218]

[ATTACH=CONFIG]11390[/ATTACH]10 kí tự chưa?

cậu giải thích cách làm dc ko ????:happy:

[12520222]

cậu giải thích cách làm dc ko ????:happy:

đây anh giải.jpg

[11520218]

đây anh [ATTACH=CONFIG]11399[/ATTACH]

hiểu rồi cám ơn em nha:happy:

[11520112]

phải trình bày như vậy mới đúng nè Long
Untitled.png
p/s: mấy ô trống phía trên là vô cùng á, mất công chèn cái kí kiệu :v

[11520112]

giải thích nè:
- a không nằm trong cột dọc: lí do là a là điểm xuất phát, mình ko thể xuất phát từ a đến a được.
- vô cùng: không có con đường nào dẫn từ đỉnh x -> đỉnh y bất kì.
- (4,1), (3,a),...: khoảng cách từ a đến đỉnh tiếp theo của đồ thị.
- dấu "-" có nghĩa là do mình đã chọn đỉnh đó là đỉnh kế tiếp rồi nên bỏ chọn đỉnh này cho lượt đi tiếp theo.
- chọn đường đi ngắn nhất. nên trong bảng mình chọn giá trị nhỏ nhất để chọn đỉnh đi kế tiếp.
- có thể sẽ thắc mắc: tại sao khoảng cách từ c -> e là (10,c): thì do a -> c = 3, c -> e = 7 thì (10,c) là 3 + 7 = 10 tức là quãng đường đi từ a -> e. tương tự cho các trường hợp tiếp theo (9,d), (14,d),...
- thêm 1 trường hợp ở cột f, ta có 3 giá trị (14,d) liên tiếp nhưng tại sao ở hàng g lại là (12,g): lí do: khoảng cách g -> f = 1, mà quãng đường mình đã đi là a->b->d->g = 11, nên ta sẽ có từ g -> f =1 thì quãng đường từ a -> f = 11 + 1 =12 <14.
nhìn vào bảng trên ta có kết quả là: đường đi ngắn nhất đi từ a-> z là: a->b->d->g->z=15

[11520218]

giải thích nè:
- a không nằm trong cột dọc: lí do là a là điểm xuất phát, mình ko thể xuất phát từ a đến a được.
- vô cùng: không có con đường nào dẫn từ đỉnh x -> đỉnh y bất kì.
- (4,1), (3,a),...: khoảng cách từ a đến đỉnh tiếp theo của đồ thị.
- dấu "-" có nghĩa là do mình đã chọn đỉnh đó là đỉnh kế tiếp rồi nên bỏ chọn đỉnh này cho lượt đi tiếp theo.
- chọn đường đi ngắn nhất. nên trong bảng mình chọn giá trị nhỏ nhất để chọn đỉnh đi kế tiếp.
- có thể sẽ thắc mắc: tại sao khoảng cách từ c -> e là (10,c): thì do a -> c = 3, c -> e = 7 thì (10,c) là 3 + 7 = 10 tức là quãng đường đi từ a -> e. tương tự cho các trường hợp tiếp theo (9,d), (14,d),...
- thêm 1 trường hợp ở cột f, ta có 3 giá trị (14,d) liên tiếp nhưng tại sao ở hàng g lại là (12,g): lí do: khoảng cách g -> f = 1, mà quãng đường mình đã đi là a->c->b->d->e->g = 11, nên ta sẽ có từ g -> f =1 thì quãng đường từ a -> f = 11 + 1 =12 <14.
nhìn vào bảng trên ta có kết quả là: đường đi ngắn nhất đi từ a-> z là: a->c->b->d->e->g->f->z=15

cám ơn hoa nhe:sogood:

[11520112]

cám ơn hoa nhe:sogood:

:haha: không có gì, thi 10 điểm nhớ hậu tạ được rồi
lần sau gọi tên nhớ viết hoa chũ đầu tiên là nha :baffle:

[11520218]

:haha: không có gì, thi 10 điểm nhớ hậu tạ được rồi
lần sau gọi tên nhớ viết hoa chũ đầu tiên là nha :baffle:

ờ quên, để sửa lại :brick:

[12520222]

giải thích nè:
- a không nằm trong cột dọc: lí do là a là điểm xuất phát, mình ko thể xuất phát từ a đến a được.
- vô cùng: không có con đường nào dẫn từ đỉnh x -> đỉnh y bất kì.
- (4,1), (3,a),...: khoảng cách từ a đến đỉnh tiếp theo của đồ thị.
- dấu "-" có nghĩa là do mình đã chọn đỉnh đó là đỉnh kế tiếp rồi nên bỏ chọn đỉnh này cho lượt đi tiếp theo.
- chọn đường đi ngắn nhất. nên trong bảng mình chọn giá trị nhỏ nhất để chọn đỉnh đi kế tiếp.
- có thể sẽ thắc mắc: tại sao khoảng cách từ c -> e là (10,c): thì do a -> c = 3, c -> e = 7 thì (10,c) là 3 + 7 = 10 tức là quãng đường đi từ a -> e. tương tự cho các trường hợp tiếp theo (9,d), (14,d),...
- thêm 1 trường hợp ở cột f, ta có 3 giá trị (14,d) liên tiếp nhưng tại sao ở hàng g lại là (12,g): lí do: khoảng cách g -> f = 1, mà quãng đường mình đã đi là a->c->b->d->e->g = 11, nên ta sẽ có từ g -> f =1 thì quãng đường từ a -> f = 11 + 1 =12 <14.
nhìn vào bảng trên ta có kết quả là: đường đi ngắn nhất đi từ a-> z là: a->c->b->d->e->g->f->z=15

hình như bài giải chị có vấn đề, độ dài đường đi ngắn nhất từ a->z = 15 là đúng rồi nhưng không phải đường đi là a->c->b->d->e->g->f->z và đường đi này không phải =15

[11520139]

hình như bài giải chị có vấn đề, độ dài đường đi ngắn nhất từ a->z = 15 là đúng rồi nhưng không phải đường đi là a->c->b->d->e->g->f->z và đường đi này không phải =15

Đúng như bạn nói. hi đường đi ngắn nhất là a->b->d->g->z

[11520112]

hình như bài giải chị có vấn đề, độ dài đường đi ngắn nhất từ a->z = 15 là đúng rồi nhưng không phải đường đi là a->c->b->d->e->g->f->z và đường đi này không phải =15

hehe, viết nhầm :3
cám ơn em, đã chỉnh sửa