Hotline: 024.62511017

024.62511081

  Trang chủ   Sản phẩm   Phần mềm Dành cho nhà trường   Phần mềm Hỗ trợ học tập   Kho phần mềm   Liên hệ   Đăng nhập | Đăng ký

Tìm kiếm

School@net
 
Xem bài viết theo các chủ đề hiện có
  • Hỗ trợ khách hàng (474 bài viết)
  • Hoạt động của công ty (527 bài viết)
  • Thông tin khuyến mại (73 bài viết)
  • Sản phẩm mới (216 bài viết)
  • Mô hình & Giải pháp (145 bài viết)
  • IQB và mô hình Ngân hàng đề kiểm tra (116 bài viết)
  • TKB và bài toán xếp Thời khóa biểu (236 bài viết)
  • Học tiếng Việt (175 bài viết)
  • Dành cho Giáo viên (379 bài viết)
  • Download - Archive- Update (156 bài viết)
  • Cùng Học (93 bài viết)
  • Learning Math: Tin học hỗ trợ học Toán trong nhà trường (72 bài viết)
  • Thông tin tuyển dụng (3 bài viết)
  • School@net 15 năm (18 bài viết)
  • Mỗi ngày một phần mềm (7 bài viết)
  • Dành cho cha mẹ học sinh (114 bài viết)
  • Khám phá phần mềm (30 bài viết)
  • GeoMath: Giải pháp hỗ trợ học dạy môn Toán trong trường phổ thông (34 bài viết)
  • Phần mềm cho em (13 bài viết)
  • Tin học và Toán học (116 bài viết)
  • Phần mềm Quản lý đào tạo nhà trường (69 bài viết)
  • Làm quen với Tin học (17 bài viết)
  • Vui học đường (1 bài viết)
  • Bài học trực tuyến (60 bài viết)
  • Các vấn đề giáo dục (2 bài viết)
  • Các Thuật toán hay (1 bài viết)
  • TKBU và bài toán thời khóa biểu trường đại học (11 bài viết)
  • Xem toàn bộ bài viết (3170 bài viết)
  •  
    Đăng nhập/Đăng ký
    Bí danh
    Mật khẩu
    Mã kiểm traMã kiểm tra
    Lặp lại mã kiểm tra
    Ghi nhớ
     
    Quên mật khẩu | Đăng ký mới
    
     
    Giỏ hàng

    Xem giỏ hàng


    Giỏ hàng chưa có sản phẩm

     
    Bản đồ lưu lượng truy cập website
    Locations of visitors to this page
     
    Thành viên có mặt
    Khách: 5
    Thành viên: 0
    Tổng cộng: 5
     
    Số người truy cập
    Hiện đã có 83813791 lượt người đến thăm trang Web của chúng tôi.

    Tìm đường đi ngắn nhất với định tuyến Dijkstra

    Ngày gửi bài: 23/01/2009
    Số lượt đọc: 283242

    Bài viết này xin giới thiệu với các bạn mới làm quen với tin học và thuật giải một thuật toán đơn giản nhưng lại có hiệu quả rất lớn trong việc tìm đường đi ngắn nhất trong đồ thị. Đó là thuật toán Dijkstra. Đây là thuật toán đã đăng tải trên tạp chí tin học & nhà trường từ những số đầu tiên nhưng bài viết này sẽ đăng tải đầy đủ về bài toán, phương thức đưa ra thuật giải cũng như đoạn chương trình đầy đủ. Rất thích hợp với những bạn mới làm quen với những thuật toán kinh điển.

    Dijkstra là thuật toán định tuyến đơn giản để tìm đường đi ngắn nhất giữa 2 điểm bất kỳ. Không mất tính tổng quát, ta coi mỗi điểm (nút mạng) là một đỉnh của một đồ thị, ta sẽ dùng thuật toán Dijkstra để giải quyết bài toán tìm đường đi ngắn nhất giữa 2 điểm như sau:

    Bài toán: Cho đồ thị G với tập đỉnh V và tập các cạnh E (đồ thị có hướng hoặc vô hướng). Mỗi cạnh của đồ thị được gán một nhãn (giá trị không âm), nhãn này còn được gọi là giá trị của cạnh. Cho trước một đỉnh xác định v, gọi là đỉnh nguồn. Tìm đường đi ngắn nhất từ đỉnh v đến các đỉnh còn lại của G. (Tức là tìm đường đi từ v đến các đỉnh còn lại với tổng các giá của các cạnh trên đường đi là nhỏ nhất). Nếu như đồ thị có hướng thì đường đi này là đường đi có hướng.

    Thuật toán Dijkstra: Ta có thể giải bài toán bằng cách xác định một tập hợp S chứa các đỉnh mà khoảng cách ngắn nhất từ nó đến đỉnh nguồn v đã biết. Khởi đầu S = { V }. Sau đó tại mỗi bước ta sẽ thêm vào S các đỉnh mà khoảng cách từ nó đến v là ngắn nhất. Với giả thiết rằng mỗi cung có một giá trị không âm thì ta luôn luôn tìm được một đường đi ngắn nhất như vậy mà chỉ đi qua các đỉnh đã tồn tại trong S. Ðể dễ dàng chi tiết hóa giải thuật, giả sử G có n đỉnh và nhãn trên mỗi cung được lưu trong mảng C, tức là C[i, j] bằng giá trị(có thể xem là độ dài) của cung (i, j). Nếu i và j không có cung nối thì ta cho C[i, j] =Ġ. Ta sẽ dùng một mảng D có n phần tử để lưu độ dài của đường đi ngắn nhất từ v đến mỗi đỉnh của đồ thị. Khởi đầu thì giá trị này chính là độ dài cạnh (v, i), tức D[i] = C[v, i]. Tại mỗi bước của giải thuật thì D[i] sẽ lưu độ dài đường đi ngắn nhất từ đỉnh v đến đỉnh i, đường đi này chỉ đi qua các đỉnh đã có trong S.
    Ðể cài đặt giải thuật dễ dàng, ta giả sử các đỉnh của đồ thị được đánh số từ 1 đến n và đỉnh nguồn là đỉnh 1. Dưới đây là giải thuật Dijkstra để giải bài toán trên :

    procedure Dijkstra;
    begin
    S := [1] ; { S chỉ chứa đỉnh nguồn }
    for i:=2 to n do
    D[i] := C[1, i] ; { Khởi đầu các giá trị cho D }
    for i:=1 to n - 1 do
    begin
    Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ;
    Thêm w vào S ;
    for mỗi đỉnh u thuộc V - S do
    D[u] := Min (D[u], D[w] + C[w, u]) ;
    end;
    end;

    Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn nhất để có thể xây dựng lại đường đi này từ đỉnh nguồn đến các đỉnh khác, ta dùng một mảng P. Mảng này sẽ lưu P[u] = w với đỉnh u là đỉnh trước của đỉnh w trên đường đi ngắn nhất. Lúc khởi đầu ta cho P[u] = 1, với mọi u khác 1.
    Giải thuật Dijkstra ở trên sẽ được viết lại như sau :

    procedure Dijkstra ;
    begin
    S := [1] ; { S chỉ chứa đỉnh nguồn }
    for i:=2 to n do
    begin
    D[i] := C[1, i] ; { Khởi đầu các giá trị cho D }
    P[i] := 1 ; { Khởi đầu các giá trị cho P }
    end ;
    for i:=1 to n - 1 do
    begin
    Lấy đỉnh w trong V - S sao cho D[w] là nhỏ nhất ;
    Thêm w vào S ;
    for mỗi đỉnh u thuộc V - S do
    if (D[w] + C[w, u] < D [u]) then
    begin
    D[u] := D[w] + C[w, u] ; P[u] := w ;
    end ;
    end;
    end;

    Ví dụ : Áp dụng giải thuật Dijkstra cho đồ thị hình sau:



    procedure DijksTra;
     begin
    t:=false;
    t[u0]:=true;
    d[i]:=c[u0,i];{Neu khong co duong di thi d[i]=i’}
    k:=1;{Da ket nap duoc 1 dinh}
    while kdo
    begin
    {Tim min}
    min:=i’;
    for i:=1 to n do
    if (d[i]and(not t[i])then
    begin
    u:=i;
    min:=d[u]
    end;
    t[u]:=true;{thêm u vao tập đỉnh}
    inc(k);
     {Tính lại đường đi}
    for i:=1 to n do
    if d[i]>d[u]+c[u,i] then
    if not((d[i]=i’)and(d[u]=i’)and(c[u,i]=i’)) then
    begin
    d[i]:=d[u]+c[u,i];
    truoc[i]:=u
    end
    end;
    if d[v0]=i’ then
    KhongCoDuongDi
    else
    QuayLaiMangTruocDeTimDuong
    end;

    School@net (Theo THNT)



     Bản để in  Lưu dạng file  Gửi tin qua email


    Lên đầu trang

     
    CÔNG TY CÔNG NGHỆ TIN HỌC NHÀ TRƯỜNG
     
    Phòng 804 - Nhà 17T1 - Khu Trung Hoà Nhân Chính - Quận Cầu Giấy - Hà Nội
    Phone: 024.62511017 - 024.62511081
    Email: kinhdoanh@schoolnet.vn


    Bản quyền thông tin trên trang điện tử này thuộc về công ty School@net
    Ghi rõ nguồn www.vnschool.net khi bạn phát hành lại thông tin từ website này
    Site xây dựng trên cơ sở hệ thống NukeViet - phát triển từ PHP-Nuke, lưu hành theo giấy phép của GNU/GPL.