Diễn Đàn Lớp 09CT112


 
IndexPortalCalendarTrợ giúpTìm kiếmThành viênNhómĐăng kýĐăng Nhập
News & Announcements
  • Gallery
163 Số bài - 27%
82 Số bài - 13%
77 Số bài - 13%
56 Số bài - 9%
53 Số bài - 9%
43 Số bài - 7%
39 Số bài - 6%
36 Số bài - 6%
33 Số bài - 5%
33 Số bài - 5%
Similar topics
Tài khoản gmail chung cho lớp
Tue Sep 13, 2011 10:58 pm by haily2312
tên tài khoản: 09ct112@gmail.com.
password: Khongb!t

Comments: 2
Lịch thi sớm môn Cơ bản học kỳ 1 năm học 2011-2012
Tue Oct 04, 2011 9:42 am by haily2312
Theo thông báo của khoa lớp chúng ta sẽ thi môn PPNCKH vào ngày 19/11/2011 lúc 17h30 địa điểm chưa xác định. Sẽ tiếp tục cập nhật thông báo mới

Link chi tiết http://cs.lhu.edu.vn/?CID=8&NewsID=12708

Comments: 2
Lý thuyết đồ thị
Fri May 27, 2011 5:11 pm by ღ♂→√ô◦Tìnђ♥ №¹ღ
Ai có tài liệu lý thuyết đồ thị của thầy share với " love " đi nào ??? 4rum gì chán dữ vậy? Ko có cả 1 bóng ma

Comments: 3
Đề thi Online Final cho những ai không may
Thu Jun 23, 2011 10:10 am by nguyenluuphat
các bạn vào đây download về xem nhé.
www.mediafire.com/phatdeptrai
hoặc
http://www.mediafire.com/?6h9y7452s1gch9f

Comments: 0
TIN HOT...về cuộc thi Đố vui tin học năm 2011
Wed Feb 23, 2011 4:51 pm by [N]
ĐOÀN TRƯỜNG ĐH LẠC HỒNG
ĐOÀN KHOA CÔNG NGHỆ THÔNG TIN
SỐ:../../../..
ĐOÀN TNCS HỒ CHÍ MINH
Biên Hòa, ngày 20 tháng 02 năm 2011
------------------------

KẾ HOẠCH
Tổ chức Cuộc thi Đố vui tin học năm 2011



Hưởng ứng phong trào Đoàn trong nhà
trường năm 2011. Được sự cho phép của BCH Đoàn trường và Ban lãnh đạo
khoa, BCH …

[ Full reading ]
Comments: 2
CƠ HỘI CHỨNG TỎ BẢN LĨNH... tham gia nào.
Wed Feb 23, 2011 4:39 pm by [N]
Trường ĐH Lạc Hồng
Khoa Công Nghệ Thông Tin

Đoàn Trường ĐH Lạc Hồng
Biên Hòa, Ngày 21 Tháng 12 Năm 2010
-------------------------------



KẾ HOẠCH TỔ CHỨC CUỘC THI ICTCUP 2011



1. Giới thiệu về cuộc thi
Trường Đại học Lạc Hồng là một trường
thành viên của Đại học có nhiệm vụ đào tạo nguồn nhân lực công …


[ Full reading ]
Comments: 3
LichThiLan2_ChinhThuc_Ngay_18_19_20
Sat Feb 12, 2011 9:27 pm by Krong Ana
Lớp ------ Môn Thi ----- Thứ ---- Ngày Thi --- Giớ Thi --- Phòng Thi

09CT112 ---- TOÁN RỜI RẠC ---- 7 ----- 2/19/2011 --- 09H30 --- B305

09CT112 ----- TOEIC 3-NÓI --- CN ---- 2/20/2011 --- 07H30 ---- G201


Comments: 1
Lich thi lần 2 lớp 09ct112 các ngày 14-15-16-17
Fri Feb 11, 2011 1:27 pm by (™•†•[pinv_a]•†•™)
CẤU TRÚC DỮ LIỆU
thứ 2.... 14/2/2011 ......... 09H30......... B201

Toán A3
thứ 3...... 15/2/2011 ...... 09H30 D305 & D403

TOEIC 3(nghe,đọc hiểu)
thứ 4 ........ 16/2/2011 ......... 07H30..... PM6-C404

MẠNG MÁY TÍNH


[ Full reading ]
Comments: 0
Lịch Thi lại lần 2 update ngày 2-2-2011
Fri Feb 04, 2011 12:02 am by (™•†•[pinv_a]•†•™)
xem lich thi ùi thi lại nhe mấy ku.

download Tại Đây

Comments: 0

Share|

Thuật toán Dijkstra: Tìm đường đi ngắn nhất trên đồ thị có trọng số.

Xem chủ đề cũ hơn
Xem chủ đề mới hơn
Go down
Tác giảThông điệp
[N]

Tổng số bài gửi : 39
Join date : 17/01/2011
Tài Sản của : [N]
Bài gửiTiêu đề: Thuật toán Dijkstra: Tìm đường đi ngắn nhất trên đồ thị có trọng số. Fri Apr 08, 2011 10:08 pm

ღ...............(¯™º•º†•»-»(¯`† Lớp 09CT112 Forum †´¯)«-«•†º•™¯)...............ღ
Thuật toán Dijkstra: Tìm đường đi ngắn nhất

Bài toán:

Cho G = (V, E) đơn, liên thông, có trọng số dương (w(uv) > 0 với mọi u khác v). Tìm đường đi ngắn nhất từ u0 đến v và tính khoảng cách d(u0,v).

Phương pháp:

Xác định tuần tự các đỉnh có khoảng cách đến u0 từ nhỏ đến lớn.

Trước tiên đỉnh có khoảng cách nhỏ nhất đến u0 là u0.
Trong V\{u0} tìm đỉnh có khoảng cách đến u0 nhỏ nhất (đỉnh này phải là một trong các đỉnh kề với u0), giả sử đó là u1.
Trong V\{u0, u1} tìm đỉnh có khoảng cách đến u0 nhỏ nhất (đỉnh này phải là một trong các đỉnh kề với u0 hoặc u1), giả sử đó là u2.
Tiếp tục như trên cho đến bao giờ tìm được khoảng cách từ u0 đến mọi đỉnh.

Nếu G có n đỉnh thì: 0 = d(u0,u0) < d(u0,u1) ≤ d(u0,u2) ≤ … ≤ d(u0,un-1)

Thuật toán Dijkstra

Bước1:

i := 0
S := V\{u0}
L(u0) := 0
Với mọi v ∈ S, L(v) := ∞ và được đánh dấu bởi (∞,-)
Nếu n = 1 thì xuất d(u0,u0) = 0 = L(u0)

Bước 2:

Với mọi v ∈ S và kề với ui (nếu đồ thị có hướng thì v là đỉnh sau của ui),
L(v) := min{L(v), L(ui) + w(uiv)}
Xác định k := min{L(v), v ∈ S}
Nếu k = L(vj) thì xuất d(u0,vj) = k và đánh dấu vj bởi (L(vj),ui)
ui+1 := vj
S := S\{ui+1}

Bước 3:

i := i + 1
Nếu i = n - 1 thì kết thúc, nếu không thì quay lại Bước 2.

(Nguồn: Tài liệu ôn tập Toán rời rạc - TS. Nguyễn Viết Đông)

Tham Khảo:
http://forums.congdongcviet.com/showthread.php?t=18499
http://vi.wikipedia.org/wiki/Thu%E1%BA%ADt_to%C3%A1n_Dijkstra

Ngoài ra còn nhiều thuật toán khác các bạn có thể tìm trên GOOLE.
Về Đầu Trang Go down
Xem lý lịch thành viên

Thuật toán Dijkstra: Tìm đường đi ngắn nhất trên đồ thị có trọng số.

Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang
Trang 1 trong tổng số 1 trang

* Viết tiếng Việt có dấu, là tôn trọng người đọc.
* Chia sẻ bài sưu tầm có ghi rõ nguồn, là tôn trọng người viết.
* Thực hiện những điều trên, là tôn trọng chính mình.
...-Nếu chèn smilies có vấn đề thì bấm A/a trên phải khung viết bài-...
Permissions in this forum:Bạn không có quyền trả lời bài viết
Diễn Đàn Lớp 09CT112 :: --o0o--GÓC HỌC TẬP--o0o-- :: ● Các Môn Học ● :: Thuật Giải-