TRƯỜNG ĐẠI HỌC ĐIỆN LỰC
KHOA CÔNG NGHỆ THÔNG TIN

BÁO CÁO CHUYÊN ĐỀ HỌC PHẦN
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT NÂNG CAO

ĐỀ TÀI:

Thuật tốn Dijkstra tìm đường đi ngắn nhất trên đồ thị
Sinh viên thực hiện

: CẤN QUANG TRIỀU
NGUYỄN THỊ THẢO MINH

Giảng viên hướng dẫn : NGUYỄN THỊ THANH TÂN
Ngành

: CƠNG NGHỆ THƠNG TIN

Chun ngành

: CƠNG NGHỆ PHẦN MỀM

Lớp

: D13-CNPM3

Khóa

: 2018-2022

Hà Nội, tháng 06 năm 2020


PHIẾU CHẤM ĐIỂM
Sinh viên thực hiện:
ST
T

Họ và tên sinh viên

1

Cấn Quang Triều

2

Nguyễn Thị Thảo Minh

Nội dung thực hiện

Điểm

Chữ kí

Giảng viên chấm:
Họ và tên

Giảng viên chấm 1 :

Giảng viên chấm 2 :


Chữ ký

Ghi chú


Mục lục
LỜI CẢM ƠN
LỜI NÓI ĐẦU
CHƯƠNG I : TỔNG QUAN VỀ THUẬT TỐN TÌM ĐƯỜNG ĐI NGẮN NHẤT
VÀ THUẬT TỐN DIJKSTRA
1.Đường đi ngắn nhất trên đồ thị
2.Thuật toán Dijkstra
3.Giải thuật
4.Độ phức tạp
5.Lưu đồ thuật tốn

CHƯƠNG II : BÀI TỐN TÌM ĐƯỜNG ĐI NGẮN NHẤT QUA
NHIỀU ĐIỂM VÀ PHƯƠNG HƯỚNG GIẢI QUYẾT
1. Ý tưởng bài tốn
2. Phương hướng giải quyết
3. Mơ tả bài toán

CHƯƠNG III: GIỚI THIỆU VỀ GIAO DIỆN VÀ MƠ PHỎNG PHẦN
MỀM
1.Ngơn ngữ sử dụng
2.Hướng dẫn sử dụng
 Giao diện chính
 Cách sử dụng


3.Cấu tạo chương trình
3.1. Cấu tạo


3.2. Source Code

LỜI CẢM ƠN
Lời đầu tiên em xin chân thành cảm ơn các thầy cô trong Khoa Công Nghệ
Thông Tin Trường Đại Học Điện Lực đã trang bị cho em những kiến thức cơ bản
cần thiết để em có thể thực hiện tốt báo cáo chuyên đề này.
Trong thời gian làm báo cáo môn học, em đã nhận được nhiều sự giúp đỡ,
đóng góp ý kiến và chỉ bảo nhiệt tình của thầy cơ, gia đình và bạn bè. Em xin chân
thành cảm ơn cô giáo Nguyễn Thị Thanh Tân đã tận tình giúp đỡ, hướng dẫn và chỉ
bảo em trong suốt quá trình học tập, nghiên cứu.
Mặc dù em đã có sự cố gắng, nhưng trong khoảng thời gian cho phép cũng
như hạn chế về kiến thức nên Báo cáo chuyên đề này của em không thể tránh khỏi
những kiến thức thiếu sót. Chính vì vậy, em rất mong nhận được sự góp ý của các
thầy cơ giáo và bạn bè.
Chúng em xin chân thành cảm ơn quý thầy cô giáo!

Hà Nội, ngày 31 tháng 6 năm 2020
Giảng viên hướng dẫn

Sinh viên thực hiện

Nguyễn Thị Thanh Tân

Cấn Quang Triều
Nguyễn Thị Thảo Minh



LỜI NÓI ĐẦU
Ngày nay, cùng với sự phát triển của đất nước ngành Cơng nghệ thơng tin đã có
những bước phát triển mạnh mẽ không ngừng và tin học đã trở thành chiếc chìa
khóa dẫn đến thành cơng cho nhiều cá nhân trong nhiều lĩnh vực, hoạt động. Công
nghệ thông tin là ngành sử dụng máy tính và phần mềm máy tính để chuyển đổi,
lưu trữ, bảo vệ, xử lý, truyền, và thu thập thông tin.
Trên thế giới cũng như ở Việt Nam, công nghê thông tin đã trở thành một
ngành cơng nghệ mũi nhọn, nó là một ngành khóa học kỹ thuật không thể thiếu
trong việc áp dụng vào các hoạt động xã hội như: Quản lý, kinh tế, thơng tin…
Trong khoa học máy tính và trong tốn học, thuật tốn tìm đường đi ngắn
nhất trong đồ thị là một bài toán thường được vận dụng trong các ứng dụng tin học,
và là một yêu cầu không thể thiếu trong khi thiết kế các phần mềm như xây dựng
bản đồ mạng lưới giao thông.
Mặc dù rất cố gắng để hồn thành đề tài, xong thời gian có hạn và kiến thức
còn hạn hẹp nên bài báo cáo của chúng em cịn nhiều thiếu xót cần bổ sung. Vì
vậy, chúng em mong nhận được ý kiến đóng góp của thầy cơ và bạn bè để đề tài
này ngày càng hồn thiện tốt hơn.
Cuối cùng, chúng em xin chân thành cảm ơn cô Nguyễn Thị Thanh Tân
giảng viên bộ môn Cấu trúc dữ liệu và Giải thuật nâng cao đã tận tình chỉ bảo
hướng dẫn chúng em hồn thành đề tài nay.


CHƯƠNG I : TỔNG QUAN VỀ THUẬT TỐN TÌM ĐƯỜNG ĐI
NGẮN NHẤT DIJKSTRA
1.Đường đi ngắn nhất trên đồ thị
Nếu đồ thị biểu diễn một mạng lưới giao thơng, thì người ta khơng chỉ quan
tâm tới việc có tồn tại đường đi từ một đỉnh này tới đỉnh khác hay không, mà người
ta còn quan tâm tới con đường tối ưu nhất, ngắn nhất có thể.
Trong lý thuyết đồ thị, bài toán đường đi ngắn nhất giữa hai đỉnh cho trước là bài

tốn tìm một đường đi giữa chúng sao cho tổng các trọng số của các cạnh tạo nên
đường đi đó là nhỏ nhất. Định nghĩa một cách hình thức, cho trước một đồ thị có
trọng số G=(V,E,w)G=(V,E,w) (nghĩa là một tập đỉnh V, một tập cạnh E, và một
hàm trọng số có giá trị thực w : E → R), cho trước một đỉnh u thuộc V, tìm một
đường đi P từ u tới một đỉnh v thuộc V sao cho:

∑p∈Pw(p)
nhỏ nhất trong tất cả các đường đi từ u tới v. Bài toán đường đi ngắn nhất giữa mọi
cặp đỉnh là một bài tốn tương tự, trong đó ta phải tìm các đường đi ngắn nhất cho
mọi cặp đỉnh u và v.
Các thuật toán thường được dùng để giải quyết những bài tốn này là:
•

Thuật tốn Dijkstra - giải bài toán bài toán đường đi ngắn nhất giữa hai đỉnh
cho trước nếu tất cả các trọng số đều khơng âm. Thuật tốn này có thể tính
tốn tất cả các đường đi ngắn nhất từ một đỉnh xuất phát cho trước s tới mọi

đỉnh khác mà không làm tăng thời gian chạy.
• Thuật tốn Bellman-Ford - giải bài tốn bài toán đường đi ngắn nhất giữa
hai đỉnh cho trước trong trường hợp trọng số có thể có giá trị âm.


•

Giải thuật tìm kiếm A* giải bài tốn bài tốn đường đi ngắn nhất giữa hai

đỉnh cho trước sử dụng heuristics để tăng tốc độ tìm kiếm
• Thuật tốn Floyd-Warshall - giải bài toán đường đi ngắn nhất cho mọi cặp
đỉnh.
• Thuật tốn Johnson - giải bài tốn đường đi ngắn nhất cho mọi cặp đỉnh, có

thể nhanh hơn thuật tốn Floyd-Warshall trên các đồ thị thưa.
• Lý thuyết nhiễu (Perturbation theory) - tìm đường đi ngắn nhất địa phương
(trong trường hợp xấu nhất)

2.Thuật toán Dijkstra
Thuật toán Dijkstra, mang tên của nhà khoa học máy tính người Hà Lan Edsger
Dijkstra vào năm 1956 và ấn bản năm 1959.
Trong trường hợp đồ thị G=(V,E,w)G=(V,E,w) có trọng số trên các cạnh khơng âm,
ta có thuật tốn Dijkstra để tìm đường đi ngắn nhất từ đỉnh xuất phát s tới các đỉnh
khác của đồ thị.
Thuật toán thường được sử dụng trong định tuyến với một chương trình con trong
các thuật tốn đồ thị hay trong cơng nghệ Hệ thống định vị tồn cầu (GPS).

3.Giải thuật
Thuật tốn có thể được mơ tả bằng thủ tục Dijkstra như sau:
-Bước khởi tạo: s là đỉnh xuất phát
for v thuộc V do {
d[v] = A[s,v];
truoc[v] =s;
}


-Bước lặp:
While(V≠rỗng){
<Chọn u là đỉnh có d[u] nhỏ nhất>;
<Cố định nhãn của đỉnh u>; V = V\{u};
for v thuộc V do {
if (d[v]> d[u] +A[u,v]) {
d[v] = d[u] +A[u,v];
truoc[v] = u;

}
}
}
-Bước trả về kết quả : Return(d (s , t) );
*Sau đây là các bước của giải thuật Dijkstra:
B1.

Khởi tạo: Đặt kv:= false ∀v ∈ V; dv:= ∞,∀v ∈ V \ {a}, da:=0

B2.

Chọn v ∈ V sao cho kv = false và dv = min {dt / t∈ V, kt = false}
Nếu dv = ∞ thì kết thúc, khơng tồn tại đường đi từ a đến b.

B3.

Đánh dấu đỉnh v, kv:= true.

B4.

Nếu v = b thì kết thúc và db là độ dài đường đi ngắn nhất từ a đến b.

Ngược lại nếu v ≠ b sang B5.
B5.

Với mỗi đỉnh u kề với v mà ku = false, kiểm tra

Nếu du > dv + w(v,u) thì du:= dv + w(v,u)
Ghi nhớ đỉnh v: pu:= v. Quay lại B2.


4. Độ phức tạp


Thuật tốn Dijkstra bình thường sẽ có độ phức tạp là O(n2+m)O(n2+m), do ta phải
duyệt n lần (đối với n đỉnh), mỗi lần duyệt lại phải duyệt qua n đỉnh để tìm đỉnh có
kc[u] nhỏ nhất. Tuy nhiên ta có thể sử dụng kết hợp với cấu trúc heap hoặc set, khi
đó độ phức tạp sẽ là O((m+n)log(n))O((m+n)log(n)), nếu dùng Fibonacci thì độ
phức tạp giảm xuống cịn O(m+nlogn)O(m+nlogn). Trong đó m là số cạnh, n là số
đỉnh của đồ thị đang xét.

5.Lưu đồ thuật toán


Begin

n, C = (cij), a, z

≤

∈

L(z)

S

Đ

∈
S


∈
Đ

L(x) = min(L(x), L(v) + c(v,x))


End

Chương II : BÀI TỐN TÌM ĐƯỜNG ĐI NGẮN NHẤT QUA
NHIỀU ĐIỂM VÀ PHƯƠNG HƯỚNG GIẢI QUYẾT
1. Ý tưởng bài tốn
Ta có mảng kc[u] là khoảng cách ngắn nhất từ đỉnh s tới đỉnh u trên đồ thị.
Ban đầu kc[s] = 0, các giá trị khác bằng dương vô cực. Ta sẽ lấy đỉnh u có kc[u]
nhỏ nhất vào thời điểm hiện tại, và sử dụng khoảng cách của nó để cập nhật
khoảng cách ngắn nhất của các đỉnh xung quanh. Với một đỉnh u bất kì, vì nó được
cập nhật bởi các đường đi ngắn nhất của các đỉnh xung quanh nó, nên bản thân
đường đi của nó cũng là ngắn nhất.

2. Phương hướng giải quyết
B1: Lấy thông tin điểm gốc và các điểm đến.
B2: Sử dụng thuật toán Dijkstra để tìm đường đi từ gốc đến các điểm lân
cận
.
B3: Sắp xếp các điểm theo chi phí và tìm điểm cần đến có chi phí nhỏ nhất.
B4: Kiểm tra xem cịn điểm cần đến hay khơng? Nếu cịn, thay điểm gốc
bằng điểm cần đến có chi phí nhỏ nhất và lặp lại B2 (Đệ quy).
B5: Lấy lại đường đi từ điểm gốc đến các điểm đến, sử dụng các thuật tốn
đồ họa máy tính để vẽ đường đi lên bản đồ.

3. Mơ tả bài tốn

Ngun lý tối ưu là nếu tồn tại một đường đi ngắn nhất từ đỉnh I đến đỉnh J
và đỉnh K nằm trên con đường đi này thì ta phải có các đường đi từ đỉnh I đến đỉnh
K và đường đi từ đỉnh K đến đỉnh J là những đường đi ngắn nhất.


Trong các giải thuật sau, ta dùng ma trận có chiều dài L để chứa chiều dài các
cung, chiều dài cung là một số không âm ( lớn hơn hay bằng 0 ) ta có:
L[ i , j ] : = 0 với mọi i = 1,2 …, n
L[ i , j ] : > 0 nếu tồn tại một cung từ đỉnh A đến đỉnh B
L[ i , j ] = vô cực nếu không tồn tại một cung từ đỉnh I đến đỉnh J

CHƯƠNG III: GIỚI THIỆU VỀ GIAO DIỆN VÀ MƠ PHỎNG
PHẦN MỀM
1.Ngơn ngữ sử dụng
-Java (phiên âm Tiếng Việt: "Gia-va") là một ngơn ngữ lập trình hướng đối
tượng (OOP) và dựa trên các lớp (class). Khác với phần lớn ngơn ngữ lập trình
thơng thường, thay vì biên dịch mã nguồn thành mã máy hoặc thông dịch mã
nguồn khi chạy, Java được thiết kế để biên dịch mã nguồn thành bytecode,
bytecode sau đó sẽ được mơi trường thực thi (runtime environment) chạy.
-Java được vay mượn nhiều từ C & C++ nhưng có cú pháp hướng đối tượng đơn
giản hơn và ít tính năng xử lý cấp thấp hơn. Do đó việc viết một chương trình bằng
Java dễ hơn, đơn giản hơn, đỡ tốn công sửa lỗi hơn. Nhưng về lập trình hướng đối
tượng thì Java phức tạp hơn.
-Giới thiệu về Swing. Java Foundation Classes (JFC) được được giới thiệu trong
phiên bản 2.0 (Java Development Kit – JDK 2.0), là một framework hỗ trợ lập
trình giao diện đồ hoạ (Graphical Interface) với thư viện Swing.
-Swing là một framework được thiết kế theo mơ hình MVC (Model View
Controller), hỗ trợ công nghệ gọi là “Pluggable-Look-And-Feel” cho phép các



thành phần giao diện có thể được hiển thị trên bất ký hệ điều hành nào như
Windows, Mac OS, Linux, …

2.Hướng dẫn sử dụng
 Giao diện chính:

 Cách sử dụng:
• Nhấn vào nút chọn OpenFile và chọn tới file dữ liệu cần tính tốn.
• Nhấn vào nút LoadFile để mở file
• Chọn hai đỉnh muốn tính đường đi và ấn tính.
• Có hai nút tính: RunStep và RunAll

+RunStep : tính đường đi từ 1 điểm đến 1 điểm nào đó của đồ thị
+RunAll: tính đường đi từ 1 điểm đến mọi điểm trên đồ thị
• Kết quả tính tốn sẽ hiển thị trong bảng LogAll và LogStep.
• Nếu muốn xóa toàn bộ dữ liệu đã load vào từ file và kết quả tính tốn. Chọn
nút Reset
• Ấn ‘Thốt’ để thốt chương trình.


3.Cấu tạo chương trình
3.1. Cấu tạo
Chương trình được cấu tạo từ 3 package : UI, Logic, Main

-UI: Là package dùng để xây dựng giao diện và xử lí các yêu cầu mà người
dùng thao tác, gồm 5 class.
+Class chính : DijkstraPanel.java
-Logic: là package dùng để thực hiện chức năng tìm đường đi ngắn nhất và lưu
trữ ma trận trọng số được load vào chương trình.
+Class chính : Dijkstra.java

-Main: là package dùng để bắt đầu chương trình
+Class chính : Main.java
3.2. Source Code
a. Class DijkstraPanel.java


Phương thức addComp() : Tạo giao diện chương trình
@Override
public void addComp() {
Font f = new Font("Tahoma", Font.BOLD, 15);
Font fs = new Font("Tahoma", Font.PLAIN, 20);
fileMenu.setFont(f);
helpMenu.setFont(f);
fileMenu.add(createMenuItem("New", KeyEvent.VK_N, Event.CTRL_MASK));
fileMenu.add(createMenuItem("Open", KeyEvent.VK_O, Event.CTRL_MASK));
fileMenu.add(createMenuItem("Save", KeyEvent.VK_S, Event.CTRL_MASK));
fileMenu.add(createMenuItem("Exit", KeyEvent.VK_X, Event.CTRL_MASK));
helpMenu.add(createMenuItem("Help", KeyEvent.VK_H, Event.CTRL_MASK));
helpMenu.add(createMenuItem("About", KeyEvent.VK_A,
Event.CTRL_MASK));
menuBar = new JMenuBar();
menuBar.setSize(100, 30);
menuBar.setBackground(Color.GRAY);
menuBar.add(fileMenu);
menuBar.add(helpMenu);
menuBar.setLocation(10, 10);
add(menuBar);
loadFile = createLabel(fs, "File:", menuBar.getX(), menuBar.getY() +
menuBar.getHeight() + 20, Color.RED);
add(loadFile);

tfFile = createTextField(fs, loadFile.getX() + loadFile.getWidth() + 10,
loadFile.getY() - 3,
GUI.WIDTH_FRAME / 2 - 300, Color.BLACK);
add(tfFile);


btOpen = createButton(fs, "Open File", tfFile.getX() + tfFile.getWidth() + 5,
loadFile.getY() - 3, Color.ORANGE,
BT_OPEN);
add(btOpen);
btFile = createButton(fs, "Load File", btOpen.getX() + btOpen.getWidth() + 5,
loadFile.getY() - 3,
Color.MAGENTA, BT_LOAD_FILE);
add(btFile);
choi = new Choice();
choi.setBounds(btFile.getX() + btFile.getWidth() + 20, btFile.getY(),
200, 30);
choi.add("Begin");
choi1 = new Choice();
choi1.setBounds(btFile.getX() + btFile.getWidth() + 20, btFile.getY(), 200, 30);
choi1.add("End");
btRunAll = createButton(f, "Run All", 0, 0, Color.BLACK, BT_RUN_ALL);
btRunStep = createButton(f, "Run Step", 0, 0, Color.BLACK, BT_RUN_STEP);
JPanel panelTinh = new JPanel(new GridLayout(1, 3, 30, 10));
panelTinh.setBorder(new TitledBorder("Tính Đường Đi"));
panelTinh.setSize(GUI.WIDTH_FRAME / 2 - 100, 50);
panelTinh.setLocation(btFile.getX() + btFile.getWidth() + 20, btFile.getY());
panelTinh.add(choi);
panelTinh.add(choi1);
panelTinh.add(btRunStep);

panelTinh.add(btRunAll);
add(panelTinh);
table = new JTable();
table.setBackground(Color.WHITE);
table.setForeground(Color.BLUE);
table.setFont(f);
JScrollPane jScrollPane = new JScrollPane(table);
jScrollPane.setSize(GUI.WIDTH_FRAME / 2 - 50, GUI.HEIGHT_FRAME / 2);
jScrollPane.setLocation(loadFile.getX() + 10, loadFile.getY() +
loadFile.getHeight() + 60);
add(jScrollPane);
model = new DefaultTableModel();
table.setModel(model);
JPanel paneltb = new JPanel();
titletb = createLabel(fs, "Ma Trận", 0, 0, Color.BLACK);
paneltb.setSize(jScrollPane.getWidth(), 50);
paneltb.setLocation(jScrollPane.getX(), jScrollPane.getY() - 30);
paneltb.add(titletb);
add(paneltb);
textAll = new JTextArea("Path:");
textAll.setRows(20);


textAll.setLineWrap(true);
textAll.setColumns(1);
textAll.setWrapStyleWord(true);
JScrollPane scroll = new JScrollPane(textAll);
JPanel panelRunAll = new JPanel(new BorderLayout());
panelRunAll.setBorder(new TitledBorder("Log All"));
panelRunAll.add(scroll, BorderLayout.PAGE_START);

panelRunAll.setLocation(paneltb.getX() + paneltb.getWidth() + 20,
paneltb.getY());
panelRunAll.setSize(GUI.WIDTH_FRAME / 2 - 10, GUI.HEIGHT_FRAME / 2 +
40);
add(panelRunAll);
//
//

btReset = createButton(fs, "Reset", panelRunAll.getX() +
panelRunAll.getWidth() / 2 - 100,
panelRunAll.getY() + panelRunAll.getHeight() + 10, Color.blue,
BT_RESET);
add(btReset);
btThoat = createButton(fs, "Thoát", btReset.getX() + btReset.getWidth() + 20,
btReset.getY(), Color.GREEN,
BT_THOAT);
add(btThoat);
textLog = new JTextArea("Path: ");
textLog.setRows(3);
textLog.setEditable(false);
JScrollPane scrollPath = new JScrollPane(textLog);
JPanel panelketqua = new JPanel(new BorderLayout());
panelketqua.setBorder(new TitledBorder("Log Step"));
panelketqua.add(scrollPath, BorderLayout.PAGE_START);
panelketqua.setLocation(jScrollPane.getX(), jScrollPane.getY() +
jScrollPane.getHeight() + 70);
panelketqua.setSize(GUI.WIDTH_FRAME - 50, 85);
add(panelketqua);
}


-Phương thức clickComps(): Xử lí sự kiện của chương trình
@Override
protected void clickComps(String name) {
distra = new dijkstra();
switch (name) {
case BT_LOAD_FILE:
actionLoad();
break;
case BT_RUN_ALL:
actionRunAll();
break;
case BT_OPEN:
JFileChooser fc = new JFileChooser();
int select = fc.showOpenDialog(this);
if (select == 0) {
tfFile.setText(fc.getSelectedFile().getPath());


//

System.out.println(tfFile.getText());
}
break;
case BT_RUN_STEP:
actionRunStep();
break;
case BT_RESET:
reset();
break;
case BT_THOAT:

int rs = JOptionPane.showConfirmDialog(this, "Bạn có muốn thốt
khơng?", "Thơng báo",
JOptionPane.YES_NO_OPTION);
if (rs == JOptionPane.YES_OPTION) {
System.exit(1);
} else {
return;
}
break;
default:
break;
}
}

-Phương thức reset(): Cài lại chương trình
private void reset() {
choi.removeAll();
choi.add("Begin");
choi1.removeAll();
choi1.add("End");
tfFile.setText("");
DefaultTableModel model = (DefaultTableModel) table.getModel();
model.setRowCount(0);
model.setColumnCount(0);
textAll.setText("");
textLog.setText("");
}

-Phương thức actionRunAll() và actionRunStep(): Xử lí tính tốn
private void actionRunAll() {

distra.getDuLieuTuFile(tfFile.getText());
distra.thuatToan_Dijkstra(choi.getSelectedIndex());
textAll.setText(distra.runAll());
}
private void actionRunStep() {
distra.getDuLieuTuFile(tfFile.getText());
int item = choi.getSelectedIndex();
if (choi.getSelectedItem() == "Begin" || choi1.getSelectedItem() == "End") {
JOptionPane.showMessageDialog(this, "Chưa chọn điểm đầu or điểm
đích!!!");


}

} else {
distra.thuatToan_Dijkstra(choi.getSelectedIndex());
textLog.setText(distra.runStep(choi1.getSelectedIndex()));
}

-Phương thức actionLoad(): Mở File được Open lên
private void actionLoad() {
if (tfFile.getText().isEmpty() == true) {
JOptionPane.showMessageDialog(this, "Chọn File !!!");
} else {
distra.getDuLieuTuFile(tfFile.getText());
for (int i = 0; i < distra.getSoDinh(); i++) {
choi.add(i + 1 + "");
choi1.add(i + 1 + "");
}
loadMatrix();

}
}

-Phương thức loadMatrix(): Xử lí ma trận trọng số
private void loadMatrix() {
int a[][] = distra.getG();
int infinity = 0;
int col = 1;
head = new String[a.length];
data = new String[a[0].length][a.length];
for (int i = 1; i <= a.length; i++) {
head[i - 1] = String.valueOf(i);
for (int j = 1; j <= a.length; j++) {
if (a[i - 1][j - 1] == infinity) {
data[i - 1][j - 1] = "∞";
} else {
data[i - 1][j - 1] = String.valueOf(a[i - 1][j - 1]);
}
}
}
DefaultTableModel model = new DefaultTableModel(data, head);
table.setModel(model);
table.setRowHeight(30);
System.out.println(table.getColumnCount());
if (table.getColumnCount() > col) {
for (int i = 0; i < head.length; i++) {
TableColumn tc = table.getColumnModel().getColumn(i);
tc.setPreferredWidth(50);
}
table.setAutoResizeMode(JTable.AUTO_RESIZE_OFF);

} else {
table.setAutoResizeMode(JTable.AUTO_RESIZE_ALL_COLUMNS);


}
}

b. Class dijsktra.java : Đối tượng xử lí thuật tốn

-Phương thức getDuLieuTuFile(): Đọc dữ liệu từ file ra
public boolean getDuLieuTuFile(String tenfile) {
//
String chuoifile[] = tenfile.split(".");
String path = tenfile;
try {
File file = new File(path);
if (!file.exists()) {
return false;


}
FileInputStream input = new FileInputStream(path);
InputStreamReader istream = new InputStreamReader(input);
BufferedReader reader = new BufferedReader(istream);
String sc;
// doc so dinh cua do thi , dinh bat dau , dinh dich
sc = reader.readLine();
String temp[] = sc.split(" ");
soDinh = Integer.parseInt(temp[0]);
G = new int[soDinh][soDinh];

int row = 0;
// doc matran do thi
while ((sc = reader.readLine()) != null) {
temp = sc.split(" ");
for (int col = 0; col < soDinh; col++) {
G[row][col] = Integer.parseInt(temp[col]);
}
row++;
}

}

// dong file
reader.close();
istream.close();
input.close();
} catch (Exception e) {
e.printStackTrace();
}
return true;

-Phương thức thuatToan_Dijkstra(int pointHead): Xử lí thuật tốn
public void thuatToan_Dijkstra(int pointHead) {
oo = 999999999;
this.diemDau = pointHead;
//
System.out.println(diemDau);
// Gan trong so cho cac canh khong co duong di la vo cung
for (int i = 0; i < soDinh; i++) {
for (int j = 0; j < soDinh; j++) {

if (i != j && G[i][j] == 0) {
G[i][j] = oo;
}
}
}
diemDau--;
doDai = new int[soDinh];
daXet = new int[soDinh];
dinhTruoc = new int[soDinh];
for (int i = 0; i < soDinh; i++) {
doDai[i] = oo; // khoi tao do dai tu a toi moi dinh la vo cung
daXet[i] = 0; // danh sach cac diem da xet
dinhTruoc[i] = diemDau; // dat diem bat dau cua moi diem la a
}


int i = 0;
// Khoi tao d(diemDau,diemDau)=0;
doDai[diemDau] = 0;
for (int dinh = 0; dinh < soDinh; dinh++) {
for (i = 0; i < soDinh; i++) // tim mot diem chua xet ma co duong di <
vo cung

{
if (daXet[i] != 1 && doDai[i] < oo) {
break;
}

}
if (i == soDinh)// khong co dinh nao thoa man

{
break;
}
for (int j = 0; j < soDinh; j++)// tim dinh ma co do dai la nho nhat
{
if (daXet[j] != 1 && doDai[i] > doDai[j]) {
i = j;
}
}
daXet[i] = 1; // cho i vao danh sach xet roi

}

for (int j = 0; j < soDinh; j++) // tinh lai do dai cua cac diem chua xet
{
if (daXet[j] != 1 && doDai[i] + G[i][j] < doDai[j]) {
doDai[j] = doDai[i] + G[i][j]; // thay doi do dai cua d[i,j]
dinhTruoc[j] = i; // danh dau diem truoc j la i
}
}

}

-Phương thức runAll(): Tìm đường đi giữa tất cả các đỉnh và sắp xếp theo chi phí
public String runAll() {
String path = "";
for (int dinh = 0; dinh < soDinh; dinh++) {
if (dinh != diemDau) {
// in duong di
if (doDai[dinh] < oo) {

path += "Độ dài đường đi từ đỉnh " + ((char) (diemDau
+ 65)) + " đến đỉnh " + ((char) (dinh + 65))
+ " là: " + doDai[dinh] + "\t----";
int mang[] = new int[soDinh];
int dem = 0;
int i = dinh;
while (i != diemDau) {
mang[dem++] = i;
i = dinhTruoc[i];
}
path += "\tChi tiết: " + ((char) (diemDau + 65));
for (int k = dem - 1; k >= 0; k--) {
path += "-->" + (char) (mang[k] + 65);
}


path += "\n";
} else {
path += "\t\tKhơng có đường đi từ đỉnh " + (((char)
(diemDau + 65))) + " đến đỉnh "
+ (((char) (dinh + 65)));
}
}
}
return path;
}

-Phương thức runStep(): Tìm đường đi giữa 2 điểm và sắp xếp theo chi phí
public String runStep(int pointCuoi) {
int diemCuoi = pointCuoi;

String path = "";
// in duong di
if (doDai[diemCuoi] < oo) {
path += "\t\tĐộ dài đường đi từ đỉnh " + ((char) (diemDau + 65)) + "
đến đỉnh " + ((char) (diemCuoi + 65))
+ " là: " + doDai[diemCuoi] + "\t----";
int mang[] = new int[soDinh];
int dem = 0;
int i = diemCuoi;
while (i != diemDau) {
mang[dem++] = i;
i = dinhTruoc[i];
}
path += "\tChi tiết: " + ((char) (diemDau + 65));
for (int k = dem - 1; k >= 0; k--) {
path += "-->" + (char) (mang[k] + 65);
}
} else {
path += "\t\tKhơng có đường đi từ đỉnh " + (((char) (diemDau + 65)))
+ " đến đỉnh "
+ (((char) (diemCuoi + 65)));
}
System.out.println(path);
System.out.println("\n");
}

return path;

-Phương thức inMaTran(): in ma trận


public void inMatran() {
for (int i = 0; i < soDinh; i++) {
System.out.print("\t\t");
for (int j = 0; j < soDinh; j++) {
if (G[i][j] == 0) {
System.out.print("oo\t");
} else {
System.out.print(G[i][j] + "\t");


}
}
System.out.println();
}
System.out.println();
}

-Còn lại là các phương thức get/set giá trị thuộc tính:
public int[][] getG() {
return G;
}
public void setG(int[][] g) {
G = g;
}
public int getSoDinh() {
return soDinh;
}
public int getDiemDau() {
return diemDau;
}


c. Class Main: điểm xuất phát cho bất kỳ một chương trình


Kết luận
Thông qua môn học đã giúp em nắm bắt tốt hơn về bài tốn tìm đường đi
ngắn nhất giữa hai đỉnh thơng qua thuật tốn Dijkstra. Ứng dụng được thuật tốn
vào bài tốn tìm đường đi qua nhiều điểm. Áp dụng thêm các kiến thức được học
trong quá trình học tập tại nhà trường để tạo ra được 1 ứng dụng có tác dụng trong
thực tế.