Thông tin chung

  English

  Đề tài NC khoa học
  Bài báo, báo cáo khoa học
  Hướng dẫn Sau đại học
  Sách và giáo trình
  Các học phần và môn giảng dạy
  Giải thưởng khoa học, Phát minh, sáng chế
  Khen thưởng
  Thông tin khác

  Tài liệu tham khảo

  Hiệu chỉnh

 
Số người truy cập: 37,334,413

 Thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất trên mạng mở rộng
Tác giả hoặc Nhóm tác giả: Trần Quốc Chiến*
walgreens pharmacy coupon site promo codes walgreens
Nơi đăng: Tạp chí Khoa học Công nghệ ĐHĐN; Số: Số 11(96).2015, Quyển 1;Từ->đến trang: 88;Năm: 2015
Lĩnh vực: Tự nhiên; Loại: Bài báo khoa học; Thể loại: Trong nước
TÓM TẮT
Đồ thị là công cụ toán học hữu ích ứng dụng trong nhiều lĩnh vực như giao thông, truyền thông, công nghệ thông tin, kinh tế, …. Cho đến nay, trong đồ thị mới chỉ xét đến trọng số của các cạnh, các đỉnh một cách độc lập, trong đó độ dài đường đi chỉ đơn thuần là tổng trọng số các cạnh và các đỉnh trên đường đi đó. Tuy nhiên, trong nhiều bài toán thực tế, trọng số tại một đỉnh không giống nhau với mọi đường đi qua đỉnh đó, mà còn phụ thuộc vào cạnh đi đến và cạnh đi khỏi đỉnh đó. Trong báo cáo, mô hình đồ thị mở rộng được định nghĩa.. Thuật toán Bellman-Ford là thuật toán chính tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác, trong đó trọng số cạnh có thể âm. Trên cơ sở thuật toán Bellman-Ford tìm đường đi ngắn nhất trên đồ thị truyền thống, tác giả xây dựng và chứng minh thuật toán Bellman-Ford cải biên tìm đường đi ngắn nhất từ một đỉnh đến các đỉnh khác trên mạng đồ thị mở rộng.
ABSTRACT
Graph is a powerful mathematical tool applied in many fields such as transportation, communication, informatics, economy,… So far, in ordinary graph the weights of edges and vertexes are considered independently and the length of a path is simply the sum of weights of the edges and the vertexes on this path. However, in many practical problems, weights at a vertex are not the same for all paths passing this vertex, but depend on coming and leaving edges. Therefore, a more general type of graphs, called extended graph, is defined in this work. The shortest path problem is one of the most important problems having great scientific and practical meaning. On the basis of the Bellman-Ford algorithm which finds shortest paths from a vertex to other vertexes, this paper develops a revised Bellman-Ford algorithm finding the shortest path from a vertex to other vertexes on extended networks.
© Đại học Đà Nẵng
 
 
Địa chỉ: 41 Lê Duẩn Thành phố Đà Nẵng
Điện thoại: (84) 0511 3822 041 ; Email: dhdn@ac.udn.vn