Trường Đại Học Bách Khoa Hà Nội
Khoa Điện Tử Viễn Thông
======o0o======

Ketnooi.com

ĐỒ ÁN MÔN HỌC
CƠ SỞ TRUYỀN SỐ LIỆU
Đề tài:
Định tuyến và mô phỏng trên Omnet++

Nhóm thực hiện : Nguyễn Thị Hương Đt 11-K54 20091397
Nguyễn Sơn Lâm

Đt 11-K54 20091552

Trần Văn Đô

Đt 11-K54 20090751

Nguyễn Văn Bình

Đt 11-K54 20090243

Nguyễn Duy Lâm

Đt 11-K54 20091550

Hà Nội, 11/2012

BÁO CÁO BÀI TẬP LỚN
CƠ SỞ TRUYỀN SỐ LIỆU

Đề tài: Định tuyến và mô phỏng trên Omnet

Báo cáo đồ án

1


Con tents
I- Lời nói đầu ............................................................................................................ 3
II- Phân tích chức năng và lập kế hoạch.................................................................. 4
2.1. Phân chia chức năng ........................................................................................ 4
2.2. Lập kế hoạch .................................................................................................... 4
III- Cơ sở lí thuyết và phân tích từng yêu cầu .................................................... 5
3.1. Thuật toán Dijtra ................................................................................................ 5
3.2. Mô hình mạng dùng để mô phỏng .................................................................... 7
IV- Triển khai ........................................................................................................... 8
4.1. Tạo file.ned xây dựng mạng cho quá trình mô phỏng .................................. 8
4.2. Áp dụng thuật toán Dijktra vào định tuyến đường ngắn nhất ..................... 11
4.3. Áp dụng thuật toán định tuyến cưỡng bức: ................................................... 14
4.4. Kết quả mô phỏng ............................................................................................ 16
V- Kết luận ............................................................................................................... 18

Báo cáo đồ án

2



I-

Lời nói đầu

Chúng ta đang sống trong thế kỉ 21, kỉ nguyên của khoa học kĩ thuật
và công nghệ hiện đại. Vào thời điểm này, ngành công nghiệp công nghệ
thông tin và chiếc máy vi tính nắm giữ một vai trò không thể thiếu trong
mọi lĩnh vực hoạt động của con người. Một chiếc máy tính để bàn hoạt
động độc lập là không đủ, con người muốn liên kết các máy tính lại với
nhau thành mạng máy tính để tận dụng sức mạnh xử lí, trao đổi thông
tin và chia sẻ tài nguyên. Khi mạng máy tính tăng lên cả về quy mô và số
lượng, con người lại muốn liên kết các mạng máy tính này lại với nhau.
Làm thế nào để liên kết các máy tính lại với nhau ? Làm thế nào để thông
tin có thể được trao đổi giữa các mạng máy tính cách nhau hàng trăm
cấy số ? Một bài toán cần được giải để trả lời những câu hỏi trên, đó là
bài toán định tuyến.
“Định tuyến” hiểu đơn giản là “tìm đường đi”. Trong thông tin liên lạc,
định tuyến nghĩa là chỉ ra đường đi để thông tin có thể di chuyển từ
nguồn đến đích theo cách tốt nhất. Không thể phủ nhận tầm quan trọng
của định tuyến trong truyền thông thông tin. Không có định tuyến, các
máy tính cũng như các thiết bị thông tin khác không thể trao đổi thông
tin với các mạng khác.

Báo cáo đồ án

3


II- Phân tích chức năng và lập kế hoạch
2.1. Phân chia chức năng

Dựa theo yêu cầu của bài tập lớn, chúng em chia bài toán thành 3 yêu
cầu chức năng nhỏ:
- Xây dựng và mô phỏng thuật toán định tuyến đường ngắn nhất trên
Omnet
- Xây dựng và mô phỏng thuật toán định tuyến cưỡng bức
- Áp dụng 2 thuật toán trên vào mô hình mạng và so sánh, rút ra nhận
xét về các kết quả đạt được

2.2. Lập kế hoạch
Công việc
Tìm hiểu và tổng hợp kiến thức về
thuật toán đường ngắn nhất Dijktra
Xây dựng mạng theo yêu cầu bài
toán trên Omnet++
Viết code áp dụng thuật toán Dijktra
vào mạng vừa lập
Thực hiện mô phỏng và kiểm tra
Code xây dựng thuật toán cưỡng bức
thực hiện được 1 yêu cầu

Báo cáo đồ án

Người thực hiện
Trần Văn Đô,Nguyễn Sơn Lâm,
Nguyễn Văn Bình
Nguyễn Văn Bình, Nguyễn Thị
Hương
Nguyễn Sơn Lâm
Nguyễn Duy Lâm
Nguyễn Văn Bình ,Trần Văn Đô


4


III- Cơ sở lí thuyết và phân tích từng yêu cầu
3.1. Thuật toán Dijtra
Thuật toán Dijkstra là một 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 đồ 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ạnh E (đồ thị có hướng hoặc vô
cù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.
Giải thuật :
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 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 A,tức A[i,j]=G . 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]=A[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ừ 0 đến 9 và đỉnh nguồn là đỉnh 0.

Ví Dụ:

Báo cáo đồ án

5


Chọn nút gốc là C: Q={}
d (C) = 0
=> ∏(C) = C
d (V) = ∞
với mọi V ≠ C
Nút C : Q ={C}
d(C) + W(B,C) = 4 < ∞ → d(B) = 4 , ∏(B) = C
d(C) + W(D,C) =7< ∞ → d(D) = 7 , ∏(D) = C
d(C) + W(G,C) =5< ∞ → d(G) = 5 , ∏(G) = C
Xét nút B : Q ={C,B}
d(B) + W(A,B) = 13 < ∞ → d(A) = 13 , ∏(A) = B
Xét nút G : Q ={C,B,G}
d(G) + W(A,G) = 14 >13
d(G) + W(F,G) = 15< ∞ → d(F) = 15 , ∏(F) = G
d(G) + W(H,G) = 9< ∞ → d(H) = 9 , ∏(H) = G
Xét nút D: Q={C,B,G,D}
d(D) + W(H,D) = 13 >9
d(D) + W(K,D) = 10 < ∞ → d(K) = 10 , ∏(K) = D
d(D) + W(E,D) = 9 < ∞ → d(E) = 9 , ∏(E) = D
Xét nút E: Q={C,B,G,D,E}
d(E) + W(I,E) = 18 < ∞ → d(I) = 18 , ∏(I) = E
Xét nút H: Q={C,B,G,D,E,H}
d(H) + W(K,H) = 17>10

Xét nút K: Q={C,B,G,D,E,H,K}
d(K) + W(I,K) = 13 < 18 → d(I) = 13 , ∏(I) = K
Xét nút I: Q={C,B,G,D,E,H,K,I}
d(I) + W(K,I) = 16 > 10
d(I) + W(E,I) = 22 > 9
Xét nút A: Q={C,B,G,D,E,H,K,I,A}
d(A) + W(F,A) = 16 >15
Xét nút F: Q={C,B,G,D,E,H,K,I,A,F}
Kết thúc :
Báo cáo đồ án

6


Hình : cây đường ngắn nhất từ nút nguồn C

3.2. Mô hình mạng dùng để mô phỏng
giềng.

Bậc của nút là sốlượng liên kết đi tới nút hay là số lượng nút láng

Yêu cầu bài toán:
Xây dựng cấu hình mạng gồm 10 nút có bậc trung bình bằng 2.8. Mỗi
liên kết có dung lượng 600Mbps và giả sử có khoảng cách được chọn ngẫu
nhiên trong khoảng từ 1 đến 10.
Từ những yêu cầu đặt ra ta sẽ xây dựng 10 nút mạng và dùng
(2.8*10)/2 =14 liên kết để kết nối các nút mạng với nhau. Dung lượng và
khoảng cách chính là các tham số của kênh truyền (datarate, length).

Báo cáo đồ án


7


IV- Triển khai
4.1. Tạo file.ned xây dựng mạng cho quá trình mô phỏng
- Cấu trúc 1 nút mạng:
simple Nod // một node mạng
{
parameters:
@display("i=block/routing");
gates:
inout gate[]; // cổng vào và ra đều có tên là gate
}

- Từ các node mạng lập được ra xây dựng mạng theo yêu cầu:
import ned.DatarateChannel;
import Nod;
network Network //ten mạng
{
types:
channel C0 extends ned.DatarateChannel
{

//khai báo kênh truyền

@i;@j;
double i=0; // i,j là chỉ số module Node ở 2 đầu của kênh
double j=1;
//truyền

@length; //độ dài kênh
double length @unit() = 10;
//double length @unit(km)=10 km;
delay = 100ms;
datarate = 600 Mbps; //dung lượng kênh
//@backbone;
//double cost = default(1);
//double length = default(1);

}
channel C1 extends ned.DatarateChannel // tiếp tục khai báo 13
{
@i;@j;
//kênh còn lại
double i=1;
double j=2;
@length;
double length @unit() = 4;
delay = 100ms;
datarate = 600 Mbps;
}
channel C2 extends ned.DatarateChannel
{
@i;@j;
double i=2;
double j=3;
@length;
double length @unit() = 7;
delay = 100ms;
datarate = 600 Mbps;

}
channel C3 extends ned.DatarateChannel
{
@i;@j;
double i=3;
double j=4;
Báo cáo đồ án

8


@length;
double length @unit() = 2;
delay = 100ms;
datarate = 600 Mbps;
}
channel C4 extends ned.DatarateChannel
{
@i;@j;
double i=4;
double j=9;
@length;
double length @unit() = 9;
delay = 100ms;
datarate = 600 Mbps;
}
channel C5 extends ned.DatarateChannel
{
@i;@j;
double i=8;

double j=9;
@length;
double length @unit() = 3;
delay = 100ms;
datarate = 600 Mbps;
}
channel C6 extends ned.DatarateChannel
{
@i;@j;
double i=7;
double j=8;
@length;
double length @unit() = 8;
delay = 100ms;
datarate = 600 Mbps;
}channel C7 extends ned.DatarateChannel
{
@i;@j;
double i=6;
double j=7;
@length;
double length @unit() = 4;
delay = 100ms;
datarate = 600 Mbps;
}
channel C8 extends ned.DatarateChannel
{
@i;@j;
double i=6;
double j=5;

@length;
double length @unit() = 10;
delay = 100ms;
datarate = 600 Mbps;
}
channel C9 extends ned.DatarateChannel
{
@i;@j;
double i=0;
double j=5;
@length;
double length @unit() = 3;
delay = 100ms;
datarate = 600 Mbps;
}
channel C10 extends ned.DatarateChannel
{
@i;@j;
double i=0;
Báo cáo đồ án

9


double j=6;
@length;
double length @unit() = 9;
delay = 100ms;
datarate = 600 Mbps;
}

channel C11 extends ned.DatarateChannel
{
@i;@j;
double i=2;
double j=6;
@length;
double length @unit() = 5;
delay = 100ms;
datarate = 600 Mbps;
}
channel C12 extends ned.DatarateChannel
{
@i;@j;
double i=3;
double j=7;
@length;
double length @unit() = 6;
delay = 100ms;
datarate = 600 Mbps;
}
channel C13 extends ned.DatarateChannel
{
@i;@j;
double i=8;
double j=3;
@length;
double length @unit() = 3;
delay = 100ms;
datarate = 600 Mbps;
}

submodules:
node[10] : Nod;
connections:
node[0].gate++
node[1].gate++
node[2].gate++
node[3].gate++
node[4].gate++
node[9].gate++
node[8].gate++
node[7].gate++
node[6].gate++
node[5].gate++
node[6].gate++
node[6].gate++
node[7].gate++
node[8].gate++

// sử dụng 10 Node con có kiểu Nod
<-->
<-->
<-->
<-->
<-->
<-->
<-->
<-->
<-->
<-->
<-->

<-->
<-->
<-->

C0 <--> node[1].gate++;// kết nối các Node
C1 <--> node[2].gate++; // con qua các kênh
C2 <--> node[3].gate++; // truyền vừa lập
C3 <--> node[4].gate++;
C4 <--> node[9].gate++;
C5 <--> node[8].gate++;
C6 <--> node[7].gate++;
C7 <--> node[6].gate++;
C8 <--> node[5].gate++;
C9 <--> node[0].gate++;
C10 <--> node[0].gate++;
C11 <--> node[2].gate++;
C12 <--> node[3].gate++;
C13 <--> node[3].gate++;

}

Báo cáo đồ án

10


Mô hình mạng :

- Muốn mô phỏng được quá trịnh định tuyến ta phải tạo ra một gói tin
“message” :

message
{
int
int
int
tin
}

Packet

//tên của message

source; // địa chỉ nguồn
destination; // địa chỉ đích
hopCount = 0; // số bước nhảy( số lần chuyển tiếp của gói

4.2. Áp dụng thuật toán Dijktra vào định tuyến đường ngắn
nhất

Ta xây dựng 1 file.cc phục vụ cho quá trình mô phỏng thuật toán trên
Omnet++
Để có thể áp dụng thuật toán Dijktra, yêu cầu phải cung cấp cho thuật
toán về các thông tin cấu hình mạng như: số nút mạng, số kênh truyền,
khoảng các giữa các nút. Toàn bộ các thông tin này được đọc từ một file
“input.txt”.
Ý tưởng :
Dùng thuật toán Dijktra để xây dựng cây đường ngắn nhất và hàm tiền
bối của các nút. Đường đi ngắn nhất từ nút gốc đến các nút đích chính là
đường đi theo hàm tiền bối của của nút đó qua hàm tiền bối của các nút
trung gian đến nút đích.

Báo cáo đồ án

11


File Dijktra.cc
#include <stdio.h>
#include <string.h>
#include <omnetpp.h>
#include "packet_m.h"
#define max 100 // số nút lớn nhất của mạng
using namespace std;
class Nod : public cSimpleModule // tạo và xác định class Nod trong file
{
// .ned
protected:
Packet *Nod::generateMessage(); // hàm khởi tạo gói tin
virtual void initialize(); // hàm khởi tạo
virtual void handleMessage(cMessage *msg);
public :
int A[max][max], n; //A lưu khoảng cách giữa các nút,n: số nút
int D[max], P[max];//D lưu khoảng cách ngắn nhất của nút tương ứng
// P lưu hàm tiền bối của các nút có chỉ số tương ứng
int S[max]; // tập các nút đang xét
int src; // chỉ số nút gốc của thuật toán Dijktra
};
Define_Module(Nod);
void Nod::initialize()
{
src=1; //giả sử nút gốc có chỉ số là 1

int m,x,y; //phục vụ việc đọc tệp input.txt
FILE *t1;
int temp;
t1 = fopen("input.txt","rt");
fscanf(t1,"%d",&n);
fscanf(t1,"%d",&m);
//for (int i=0;i<=n-1;i++)
for (int i=0;ifor (int j=0;jif (i==j) A[i][j]=0; // vào mảng A
else A[i][j]=200; //2 nút ko nối trực tiếp
for (int j=0;j<=m-1;j++) // sẽ cók/c vô cùng (200)
{
fscanf(t1,"%d %d %d",&x,&y,&temp);
A[x][y] = temp;
A[y][x] = temp;
}
fclose(t1);
// áp dụng thuật toán
P[src] = src; // Bước 1: chọn nút nguồn
S[src] = src; //đưa nut đó vào S( gán giá trị= chỉ số
for (int i=0; i<=n-1; i++)// bước 2: xác định k/c và hàm
{
// tiền bối của các nut còn lại theo
D[i] = A[src][i]; //nut gốc
P[i] = src;
S[i] = 10;//tai sao gan bang 10
}
int t = 1;
while (t !=n-1) // Bước 3:chon dinh tiếp theo có D nhỏ

{
// nhất
int min = 1000;
Báo cáo đồ án

12


int x;
for (int i=1; i<=n-1; i++)
{
if (S[i] == 10 && D[i]{
min = D[i];
x = i;
}
}
S[x] = x; // cho đỉnh đó vào S
for (int i=1; i<=n-1; i++) //Buoc 4:xac dinh lai d[i]
{
if (S[i]==10 && D[i]>(A[x][i] + D[x]))
{
D[i] = A[x][i] + D[x];
P[i] = x;
}
}
t++;// vòng lặp dừng khi số nút được xét là n
}
// Module 9 sends the first message
if (getIndex()==4)

{
// Boot the process scheduling the initial message as a selfmessage.
Packet *msg = generateMessage();
scheduleAt(0.0, msg);
}
}
void Nod::handleMessage(cMessage *msg) // hàm sử lí truyền nhận gói tin
{
int n= getIndex(); // xác định chỉ số node hiện tại
int g = gateSize("gate$o"); // số lượng cổng ra của node đó
int m=P[n]; // m lưu chỉ số node tiền bối của node hiện tại
double next;
// next chứa chỉ số cổng nối đến nút tiền bối
Packet *ttmsg = check_and_cast<Packet *>(msg);
if (getIndex()==src) { //nếu tin nhắn được gửi đến đích thi dừng
// Message arrived.
EV << "Message " << ttmsg << " arrived after " << ttmsg>getHopCount() << " hops.\n";
bubble("ARRIVED, starting new one!");
// delete ttmsg;
}
else { //nếu không tiếp tục gửi nó theo hàm tiền bối
double a,b;
cChannel *chan;
cGate *inoutgate;
for (int l=0;linoutgate=gate("gate$o",l);
chan=inoutgate->getChannel();
a=chan->par("i");// i,j lưu chỉ số node 2 đầu kênh nên
b= chan->par("j"); i+j-getIndex ra chỉ số nút đầu kia của kênh
if ((a+b-getIndex())==m) next=l;

}
send(ttmsg, "gate$o", next);// gửi tin nhắn qua cổng tìm
được
}
}
Báo cáo đồ án

13


Packet *Nod::generateMessage()
{
// Produce source and destination addresses.
int src = getIndex();
// our module index
int n = size();
// module vector size
int dest = 0;
if (dest>=src) dest++;
char msgname[20];
// Create message object and set source and destination field.
Packet *msg = new Packet(msgname);
msg->setSource(src);
msg->setDestination(dest);
return msg;
}

4.3. Áp dụng thuật toán định tuyến cưỡng bức:
File bt4.cc
/*

*
*
dich
*/

thuat toan dinh tuyen cuong buc 1 yeu cau tu 1 nut nguon toi 1 nut

#include <stdio.h>
#include <string.h>
#include <omnetpp.h>
#include "bt4_m.h"
class Node : public cSimpleModule
{
protected:
virtual TicTocMsg13 *generateMessage();
// virtual void forwardMessage(TicTocMsg13 *msg);
virtual void initialize();
virtual void handleMessage(cMessage *msg);
public:
double sum;
int A[10][10];
// mang hai chieu luu datarate
int P[10];
// mang luu index cua next module
int src,dest;
int next, pre;
int requestDatarate;
};
Define_Module(Node);
void Node::initialize()

// trong ham initialize() này ta se tim
duong di tu 1 src toi 1 dich luu vao mang P[].
{
src=1;dest=9;requestDatarate=400;
// thiet lap datarate cho cac kenh
for (int i=0;i<=9;i++)
Báo cáo đồ án

14


{
for (int j=0;j<=9;j++)
A[i][j]=0;
}
A[0][1]=600;A[1][2]=600;A[2][3]=600;A[3][4]=600;A[4][9]=600;A[9][8]=600;A[8
][7]=600;A[7][6]=600;A[6][5]=600;A[5][0]=600;A[0][6]=600;A[6][2]=600;
A[7][3]=600;A[3][8]=600;
A[1][0]=600;A[2][1]=600;A[3][2]=600;A[4][3]=600;A[9][4]=600;A[8][9]=600;A[7
][8]=600;A[6][7]=600;A[5][6]=600;A[0][5]=600;A[6][0]=600;A[2][6]=600;
A[3][7]=600;A[8][3]=600;
// bat dau tu module co index = 0, ta tim index cua module tiep theo luu
vao mang P[], khi nao next module = dest th? dưng lai.
next=src;pre= src;
while(next != dest)
{
int i=0;
while (i<=9)
{
if (i==pre)

{i++;}
else {
if (A[next][i]>=requestDatarate)
{ A[next][i]=A[next][i] -400;
P[next]=i;
pre=next; next=i;
break;
}
else i++;
}
}
}
// tao ban tin tai module src, truyen ban tin dang self-message
if (getIndex()==src)
{
// Boot the process scheduling the initial message as a selfmessage.
TicTocMsg13 *msg = generateMessage();
scheduleAt(0.0, msg);
}
}
void Node::handleMessage(cMessage *msg) // ham handle xu ly ban tin khi
module nhan duoc ban tin
{
int n= getIndex();
int g = gateSize("gate$o");
int m=P[n];
//double next;
EV << "m = " << m << " \n";
TicTocMsg13 *ttmsg = check_and_cast<TicTocMsg13 *>(msg);
// neu den module dich (dest) thi dung lai, bao ban tin da den noi

if (getIndex()==dest) {
// Message arrived.
EV << "Message " << ttmsg << " arrived after " <<
ttmsg->getHopCount() << " hops.\n";
bubble("ARRIVED, starting new one!");
// delete ttmsg;
Báo cáo đồ án

15


}
else {
// cac dong code duoi day de truyen ban tin nhan
duoc toi next module da xac dinh trong mang P[] trong ham initialize().
double a,b;
cChannel *chan;
cGate *inoutgate;
for (int i=0;i{
inoutgate=gate("gate$o",i);
chan=inoutgate->getChannel();
a=chan->par("i");
b= chan->par("j");
if ((a+b-getIndex())==m)
send(ttmsg, "gate$o",i);
}
}
}
TicTocMsg13 *Node::generateMessage()

// ham tao message
{
// Produce source and destination addresses.
int src = getIndex();
// our module index
char msgname[20];
sprintf(msgname, "tic-%d", src);
// Create message object and set source and destination field.
TicTocMsg13 *msg = new TicTocMsg13(msgname);
return msg;
}

4.4. Kết quả mô phỏng
Thuật toán dijkstra :
Gửi tin nhắn từ nút 4 đến nút 5, sau khi chạy chương trình ta tìm được
đường đi ngắn nhất là :
4 -> 3 -> 2 -> 6-> 5
Gửi gói tin từ 9->0:
9 -> 8 -> 7 ->6 -> 8
Các kết quả mô phỏng đều phù hợp với lí thuyết của thuật toán.

Báo cáo đồ án

16


Hình : hàm tiền bối P của các nút và đường đi theo mô phỏng

Thuật toán định tuyến cưỡng bức :

Báo cáo đồ án

17


V- Kết luận
Do thời gian thực hiện cũng như vốn hiểu biết của chúng em có hạn nên
mới chỉ xây dựng được mô hình mạng 10 nút và thực hiện được thuật toán
tìm đường ngắn nhất Dijkstra, và thực hiện mô phỏng . Chúng em chân
thành cảm ơn cô đã giúp đỡ chúng em rất nhiều , cũng như những nhận xét ,
gợi ý của cô trong thời gian qua để chúng em thực hiện bài tập lớn này. Một
lần nữa chúng em chân thành cảm ơn cô, chúc cô luôn luôn mạnh khỏe và
công tác tốt.
Tài liệu tham khảo:
1. Thuật toán Dijkstra wikipedia
2. Thuật toán Dijkstra: Tìm đường đi ngắn nhất
/>3. Thuật toán tìm đường Dijkstra
/>4. Dijstra’s algorithm
/>code for Dijkstra’s algorithm in c++
/>
Báo cáo đồ án

18