Cài đặt thuật toán Dijskstra bằng java

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:

File input2.txt

 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ả:

Read More

Lập trình hướng đối tượng với Java số 11

1. Lớp HinhCN

public class HinhCN implements Comparable

{

    private double cdai;

    private double crong;

   

    public HinhCN()

    {

    }

    public HinhCN(double cdai,double crong)

    {

        this.cdai=cdai;

        this.crong=crong;

    }

   

    public double getCRong()

    {

        return crong;

    }

     public double getCDai()

    {

        return cdai;

    }

  public void setCRong(double a)

    {

          this.crong=a;

    }

     public void setCDai(double a))

    {

         this.cdai=a;

    }

    public double tinhDT()

    {

        return cdai*crong;

    }

    public double tinhCV()

    {

        return (cdai+crong)*2;

    }

    public boolean equals(HinhCN h2)

    {

        if(this.tinhDT()==h2.tinhDT())

        {

            return true;

        }

        return false;

    }

   

    public int compareTo(Object h2)

    {

        HinhCN hcn=(HinhCN)h2;

        if(this.tinhDT()<hcn.tinhDT())

        {

            return -1;

        }

        if(this.tinhDT()==hcn.tinhDT())

        {

            return 0;

        }

        return 1;

    }

}

2.Lớp test

public class Test

{

    public static void main(String [] args)

    {

        HinhCN a=new HinhCN(5,6);

        HinhCN b=new HinhCN(5,6);

        System.out.println("Su dung phuong thuc equals: ");

        if(a.equals(b))

        {

            System.out.println("Dien tich hai hinh bang nhau");

        }

        else

        {

            System.out.println("Dien tich hai hinh khong bang nhau");

        }

       

        HinhCN c=new HinhCN(9,9);

        HinhCN d=new HinhCN(10,9);

        System.out.println("Su dung phuong thuc compareTo: ");

        if(c.compareTo(d)==-1)

        {

            System.out.println("Dien tich c<d");

        }

        else if(c.compareTo(d)==0)

        {

            System.out.println("Dien tich c=d");

        }else

        {

             System.out.println("Dien tich c>d");

        }

    }

}

3.Kết quả:

Read More

Quản Lý Sinh Viên Với Node.js

Cấu trúc gồm có các hàm :

          Hàm : getAllSV();

Hàm : addSV();

Hàm: getSV();

Hàm : hienAllSV();

Hàm: editSV();

Hàm : xoaSV();

Hàm : hienSV();

var storage = require('node-persist');

var student={id:"",name:""};

storage.initSync();

//get toan bo sv

function getAllSV()

{

          var student=storage.getItemSync('student');

          if(typeof student == "undefined")

          {

                   return [];

          }

          return student;

}

// them sv

function addSV(id,name)

{

          var sv=getAllSV();

          for(var i=0;i<sv.length;i++)

          {

                   if(sv[i].id==id)

                   {

                             console.log("Id nay da ton tai");

                             return;

                   }

          }

          sv.push({

                   id:id,

                   name:name

          });

          storage.setItemSync("student",sv);

}

//get thong sv theo id

function getSV(id)

{

          var sv=getAllSV();

          for(var i=0;i<sv.length;i++)

          {

                   if(sv[i].id==id)

                             return sv[i];

          }

}

//hien tat ca cac sv

function hienAllSV()

{

          var sv=getAllSV();

          for(var i=0;i<sv.length;i++)

          {

                   console.log(sv[i].id+ "   "+sv[i].name);

          }

}

//sua sv

function editSV(id,name)

{

          var sv=getAllSV();

          for(var  i=0;i<sv.length;i++)

          {

                   if(sv[i].id==id)

                   {

                             sv[i].name=name;

                   }

          }

          storage.setItemSync("student",sv);

}

//xoa sv theo id

function xoaSV(id)

{

          var sv=getAllSV();

          for(var i=0;i<sv.length;i++)

          {

                   if(sv[i].id==id)

                   {

                             sv.splice(i,1);

                   }

          }

          storage.setItemSync("student",sv);

}

//hien thong tin mot sv

function hienSV(sv)

{

          console.log(sv.id+ "---"+sv.name);

}

addSV(1,"Tran van Linh");

addSV(2,"Bui van A");

addSV(3,"Le tat tung");

addSV(4,"Bui Hai Nam");

addSV(5,"Tran trong nghia");

var sv=getSV(1);

console.log("Tat ca SV: ");

hienAllSV();

xoaSV(1);

console.log("Sau khi xoa sv co id=1:");

hienAllSV();

var sv=getSV(2);

console.log("Thong tin sv co id=2:");

hienSV(sv);

console.log("Thong tin sv co khi edit sv co id=2:");

editSV(2,"La Hai Nam")

var edit=getSV(2);

hienSV(edit);

   

   Kết quả khi run:

       

Read More

Vẽ chữ Z bằng vòng lặp for trong java

public class VeHinh

{

    public static void main(String[] args)

    {

        int row=7;

        int col=7;

        System.out.println("Images 1");

        for(int i=1;i<=row;i++)

        {

                if(i==1||i==row)

                {

                   for(int l=1;l<=col;l++)

                   {

                       System.out.print("* ");

                   }

                   System.out.println();

                }

                if(i!=1&&i<row)

                {

                    for(int j=1;j<i;j++)

                    {

                         System.out.print("  ");

                    }

                    System.out.println("*");  

                }

               

        }

         System.out.println("\nImages 2");

         for(int i=1;i<=row;i++)

        {

                if(i==1||i==row)

                {

                   for(int l=1;l<=col;l++)

                   {

                       System.out.print("* ");

                   }

                   System.out.println();

                }

                if(i!=1&&i<row)

                {

                    for(int j=1;j<=col-i;j++)

                    {

                         System.out.print("  ");

                    }

                    System.out.print("*");  

                    for(int k=1;k<i;k++)

                    {

                         System.out.print("  ");

                    }

                    System.out.println();

                }

               

        }

    }

}

Kết quả:
        

Read More

Demo Quản lý thời gian biểu với Android phiên bản 2

Read More

Demo quản lý thời gian biểu trên Android

Read More

Demo Quản lý thời gian biểu với android xamarin

Read More

Cài đặt thuật toán suy diễn tiến bằng Java

Giao diện chương trình: 

  

Link file exe: https://drive.google.com/file/d/0BxuqCqJeS-9XeHNMU3RFRjhyeDA/view?usp=sharing

Read More

Lập trình hướng đối tượng với C++ (Giải đề thi ngày 21/06/2016)

//Họ và tên: Trần Văn Linh

//Msv: 581597

//Lớp: K58QLTT

//Đề 29 Bài 2:Nhập vào 1 dãy n số nguyên, lưu trữ trong một hàng đợi. Đưa ra dãy số nguyên ra màn hình theo đúng thứ tự đã nhập. Tính tổng các số nguyên dương. Yêu cầu trong chương trình có sử dụng hàng đợi lưu trữ bằng danh sách liên kết đơn

#include<iostream>

using namespace std;

//khai bao lop

class DSLKD

{

          private:

                   struct node

                   {

                             int info;

                             node *link;

                   } *F,*R;

          public:

                   DSLKD();

                   ~DSLKD();

                   void cqinsert(int x);

                   int cqdelete();

                   int empty();

};

//==chuong trinh chinh

int main()

{

          DSLKD ds;

          int n;

          cout<<"Nhap so luong so nguyen: ";

          cin>>n;

          int x;

          for(int i=0;i<n;i++)

          {

                   cout<<"Nhap so nguyen: ";

                   cin>>x;

                   if(x>0)

                             ds.cqinsert(x);

          }

          int tong=0;

          cout<<"Cac so nguyen duong da nhap: ";

          while(!ds.empty())

          {

                   int tg=ds.cqdelete();

                   tong=tong+tg;

                   cout<<tg<<"  ";

          }

          cout<<"\nTong cac so nguyen duong da nhap: "<<tong<<endl;

          return 0;

}

//==dinh nghia ham

DSLKD::DSLKD():F(NULL),R(NULL)

{

                  

}

DSLKD::~DSLKD()

{

          node *P;

          if(F==R)

          {

                   delete F;

                   delete R;

          }

          while(F)

          {

                   P=F;

                   F=F->link;

                   delete P;

          }                 

}

//--------------

void DSLKD::cqinsert(int x)

{

          node *N;

          N=new node;

          N->info=x;

          N->link=NULL;

          if(R==NULL)

                   R=F=N;

          else

          {

                   R->link=N;

                   R=N;

          }

}

//--------------

int DSLKD::cqdelete()

{

          if(F==NULL)

          {

                   return 0;

          }

          int y=F->info;

          node *P;

          P=F;

          F=F->link;

          delete P;

          return y;

}

//--------------

int DSLKD::empty()

{

          if(F==NULL)

                   return 1;

          return 0;

}

//--------------

Kết quả khi chạy thử :

Read More