Bố cuc:
1. Lớp Bài toán: Cài đặt thuật toán Dijstra
2.Lớp test
1 .Lớp cài đặt thuật toán Dijkstra
BaiToan.java
package baocaovantruhoc_nhom13;
/**
*
* @TranVanLinh
*/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;
public class BaiToan
{
int soDinh;//so dinh cua do thi
int G[][];//ma tran trong so
int diemDau;//diem dau
int doDai[];//do dai toi dinh i
int daXet[];// danh dau la dinh co duong di la ngan nhat
int dinhTruoc[];//luu vet dinh truoc
int oo = 0;//gia tri vo cung
public BaiToan()
{
soDinh = 0;
G = null;
doDai = null;
daXet=null;
dinhTruoc = null;
diemDau = 0;
oo = 0;
}
//Doc du lieu
public boolean getDuLieuTuFile(String tenfile)
{
String chuoifile[]=tenfile.split(".");
String path="G://"+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]);
diemDau = Integer.parseInt(temp[1]);
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(FileNotFoundException ex)
{
System.err.println("LOi file");
}
catch (IOException ex)
{
System.err.println("Ngoai le xay ra.!");
}
return true;
}
public void thuatToan_Dijkstra()
{
oo=999999999;
//Gan trong so cho cac canh khong co duong di la vong 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
}
}
}
}
public void inDuongDi()
{
for(int dinh=0;dinh<soDinh;dinh++)
if(dinh!=diemDau)
{
//in duong di
if(doDai[dinh] < oo)
{
System.out.print("\t\tĐộ 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];
}
System.out.print("\tChi tiết: " + ((char)(diemDau+65)));
for (int k = dem - 1; k >= 0; k--) {
System.out.print("-->" + (char)(mang[k]+65));
}
}
else
{
System.out.println("\t\tKhông có đường đi từ đỉnh "+( ((char)(diemDau+65)))+" đến đỉnh " + ( ((char)(dinh+65))));
}
System.out.println("\n");
}
}
public void inDuong2Di()
{
System.out.println("Nhap dinh dich: ");
Scanner sc=new Scanner(System.in);
int diemCuoi=sc.nextInt();
//in duong di
if(doDai[diemCuoi] < oo)
{
System.out.print("\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];
}
System.out.print("\tChi tiết: " + ((char)(diemDau+65)));
for (int k = dem - 1; k >= 0; k--) {
System.out.print("-->" + (char)(mang[k]+65));
}
}
else
{
System.out.println("\t\tKhông có đường đi từ đỉnh "+( ((char)(diemDau+65)))+" đến đỉnh " + ( ((char)(diemCuoi+65))));
}
System.out.println("\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();
}
}
2. Lớp test
BaoCaoVanTruHoc_Nhom13.java
package baocaovantruhoc_nhom13;
import java.util.Scanner;
/**
*
* @TranVanLinh
*
*/
public class BaoCaoVanTruHoc_Nhom13 {
public static void main(String[] args)
{
System.out.println("\t\t\tBáo Cáo Bài Tập Lớn Môn Vận Trù Học");
System.out.println("\t\tNhóm 13\tĐề tài: Cài đặt thuật toán Dijkstra\n");
String tenTapTin;
BaiToan thuatToan;
do
{
System.out.print("\t\tNhập tên tập tin (.txt) : ");
tenTapTin=(new Scanner(System.in)).nextLine();
System.out.println("");
thuatToan=new BaiToan();
if(!thuatToan.getDuLieuTuFile(tenTapTin))
{
System.out.println("\t\tTập tin không tồn tại, Nhập lại.!");
}
}while(!thuatToan.getDuLieuTuFile(tenTapTin));
System.out.println("\t\tMa trận kề : ");
thuatToan.inMatran();
thuatToan.thuatToan_Dijkstra();
thuatToan.inDuongDi();
}
}
Vd: Tìm đường đi của từ đỉnh x1 đến tất cả các đỉnh của đồ thị sau:
7 4
0 3 5 4 2 7 5
3 0 0 0 2 0 0
5 0 0 4 0 3 0
4 0 4 0 0 0 2
2 2 0 0 0 0 4
7 0 3 0 0 0 6
5 0 0 2 4 6 0
Kết quả:
1. Lớp Bài toán: Cài đặt thuật toán Dijstra
2.Lớp test
1 .Lớp cài đặt thuật toán Dijkstra
BaiToan.java
package baocaovantruhoc_nhom13;
/**
*
* @TranVanLinh
*/
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.logging.Level;
import java.util.logging.Logger;
public class BaiToan
{
int soDinh;//so dinh cua do thi
int G[][];//ma tran trong so
int diemDau;//diem dau
int doDai[];//do dai toi dinh i
int daXet[];// danh dau la dinh co duong di la ngan nhat
int dinhTruoc[];//luu vet dinh truoc
int oo = 0;//gia tri vo cung
public BaiToan()
{
soDinh = 0;
G = null;
doDai = null;
daXet=null;
dinhTruoc = null;
diemDau = 0;
oo = 0;
}
//Doc du lieu
public boolean getDuLieuTuFile(String tenfile)
{
String chuoifile[]=tenfile.split(".");
String path="G://"+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]);
diemDau = Integer.parseInt(temp[1]);
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(FileNotFoundException ex)
{
System.err.println("LOi file");
}
catch (IOException ex)
{
System.err.println("Ngoai le xay ra.!");
}
return true;
}
public void thuatToan_Dijkstra()
{
oo=999999999;
//Gan trong so cho cac canh khong co duong di la vong 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
}
}
}
}
public void inDuongDi()
{
for(int dinh=0;dinh<soDinh;dinh++)
if(dinh!=diemDau)
{
//in duong di
if(doDai[dinh] < oo)
{
System.out.print("\t\tĐộ 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];
}
System.out.print("\tChi tiết: " + ((char)(diemDau+65)));
for (int k = dem - 1; k >= 0; k--) {
System.out.print("-->" + (char)(mang[k]+65));
}
}
else
{
System.out.println("\t\tKhông có đường đi từ đỉnh "+( ((char)(diemDau+65)))+" đến đỉnh " + ( ((char)(dinh+65))));
}
System.out.println("\n");
}
}
public void inDuong2Di()
{
System.out.println("Nhap dinh dich: ");
Scanner sc=new Scanner(System.in);
int diemCuoi=sc.nextInt();
//in duong di
if(doDai[diemCuoi] < oo)
{
System.out.print("\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];
}
System.out.print("\tChi tiết: " + ((char)(diemDau+65)));
for (int k = dem - 1; k >= 0; k--) {
System.out.print("-->" + (char)(mang[k]+65));
}
}
else
{
System.out.println("\t\tKhông có đường đi từ đỉnh "+( ((char)(diemDau+65)))+" đến đỉnh " + ( ((char)(diemCuoi+65))));
}
System.out.println("\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();
}
}
2. Lớp test
BaoCaoVanTruHoc_Nhom13.java
package baocaovantruhoc_nhom13;
import java.util.Scanner;
/**
*
* @TranVanLinh
*
*/
public class BaoCaoVanTruHoc_Nhom13 {
public static void main(String[] args)
{
System.out.println("\t\t\tBáo Cáo Bài Tập Lớn Môn Vận Trù Học");
System.out.println("\t\tNhóm 13\tĐề tài: Cài đặt thuật toán Dijkstra\n");
String tenTapTin;
BaiToan thuatToan;
do
{
System.out.print("\t\tNhập tên tập tin (.txt) : ");
tenTapTin=(new Scanner(System.in)).nextLine();
System.out.println("");
thuatToan=new BaiToan();
if(!thuatToan.getDuLieuTuFile(tenTapTin))
{
System.out.println("\t\tTập tin không tồn tại, Nhập lại.!");
}
}while(!thuatToan.getDuLieuTuFile(tenTapTin));
System.out.println("\t\tMa trận kề : ");
thuatToan.inMatran();
thuatToan.thuatToan_Dijkstra();
thuatToan.inDuongDi();
}
}
Vd: Tìm đường đi của từ đỉnh x1 đến tất cả các đỉnh của đồ thị sau:
File input2.txt
0 3 5 4 2 7 5
3 0 0 0 2 0 0
5 0 0 4 0 3 0
4 0 4 0 0 0 2
2 2 0 0 0 0 4
7 0 3 0 0 0 6
5 0 0 2 4 6 0
Kết quả:
