Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» NewBlueFx TotalFX Windows-FL | 1.11 GB
Tue Dec 17, 2013 12:42 pm by titquarra

» Celebrity.Sex.Tape.UNCUT.&.UNRATED.2012.720p.BRrip.x264.YIFY.mp4
Tue Dec 17, 2013 8:32 am by titquarra

» Maya Autodesk Personal Learning Edition 8.5
Tue Dec 17, 2013 7:47 am by titquarra

» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Thu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Thu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Mon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Tue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Tue Apr 17, 2012 10:03 pm by Admin

Shopmotion


Affiliates
free forum


Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất

View previous topic View next topic Go down

Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất

Post  Admin on Wed Jun 15, 2011 10:51 pm

Có n thành phố biết rằng đường đi giữa các thành phố (nếu có) là đường đi hai chiều. Sơ đồ mạng lưới giao thông của n thành phố cho bởi ma trận A[i,j] trong đó:
- A[i,j] là độ dài đường đi từ thành phố i đến thành phố j.
- A[i,j] = 0 nếu không có đường đi từ thành phố i đến thành phố j.
- A[i,j] = A[j,i]
- A[i,j] nguyên, không âm.
Hãy xác định đường đi ngắn nhất từ thành phố D đến thành phố C.
Dữ liệu vào: đồ thị đã liên thông và cho trong file Bai7.inp với nội dung
- Dòng đầu ghi số n là số đỉnh của một đồ thị (0- Dòng thứ hai lưu đỉnh D và đỉnh C.
- Dòng i+2 (0Dữ liệu ra: xuất ra màn hình đường đi ngắn nhất từ đỉnh D đến C và giá trị đường đi ngắn nhẩt tìm được.

Bai7.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 5
1 6 1->2->4->6
0 1 2 0 0 0
1 0 2 2 3 0
2 2 0 5 4 0
0 2 5 0 3 2
0 3 4 3 0 4
0 0 0 2 4 0

Bai7.inp Kết quả:
6 DUONG DI NGAN NHAT LA: 8
1 6 1->2->4->6
0 1 4 0 0 0
1 0 2 6 5 0
4 2 0 7 3 0
0 6 7 0 0 1
0 5 3 0 0 3
0 0 0 1 3 0

Code:
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <values.h>
#define FileIn "Bai7.inp"
/*Đọc file dữ liệu bài toán*/
void Doc_File(int**A, int &n, int &D, int &C){
  FILE*f = fopen(FileIn,"rb");
  fscanf(f,"%d%d%d",&n,&D,&C);
  cout<<"Ma Tran Lien Ket Tuong Ung.\n"<<D<<" "<<C<<endl;
  *A = new int [n];
  for(int i =0;i<n;i++) {
      A[i] = new int [n];
      for(int j =0;j<n;j++) {
        fscanf(f,"%d",&A[i][j]);
        cout<<A[i][j]<<" ";
      }
      cout<<endl;
  }
  fclose(f);
  D--; C--;
}
/*Thuật toán Dijkstra tìm đường đi ngắn nhẩt từ đỉnh D đến đỉnh C*/
void Dijkstra(int **A, int n, int D, int C) {
  char *DanhDau = new char[n];
  int *Nhan = new int[n];
  int *Truoc = new int[n];
  int XP, min;
  for(int i=0; i<n; i++){
      Nhan[i] = MAXINT;
      DanhDau[i] = 0;
      Truoc[i] = D;
  }
  Nhan[D] = 0;
  DanhDau[D] = 1;
  XP = D;
  while(XP != C){
      for(int j=0; j<n; j++)
      if(A[XP][j]>0 && Nhan[j]>A[XP][j]+Nhan[XP] && DanhDau[j]==0) {
        Nhan[j] = A[XP][j]+Nhan[XP];
        Truoc[j] = XP;
      }
      min = MAXINT;
      for(j = 0; j<n; j++)
      if(min>Nhan[j]&& DanhDau[j]==0){
        min = Nhan[j] ;
        XP = j ;
      }
      DanhDau[XP] = 1;
  }
  cout<<”Duong Di Ngan Nhat La:”<<Nhan[C]<<endl;
  cout<<C+1<<” <- “<<Truoc[C]+1;
  i = Truoc[C];
  while(i!=D){
      i = Truoc[i];
      cout<<” <- “<<i+1;
  }
}
/*Chương trình chính*/
void main() {
  int**A,n,Dau,Cuoi;
  Doc_File(A,n,Dau,Cuoi);
  Dijkstra(A,n,Dau,Cuoi);
  delete*A;
  getch();
}

Admin
Admin

Tổng số bài gửi : 782
Join date : 2009-08-15

View user profile http://hackis.forumotion.com

Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum