HACKIS - Hacking Internet Security
Would you like to react to this message? Create an account in a few clicks or log in to continue.
Search
 
 

Display results as :
 


Rechercher Advanced Search

Latest topics
» Tuyệt Kỹ Đong Giai Chân Kinh (tuyệt Kỹ cua trai)
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyThu Aug 23, 2012 5:38 am by Admin

» Tuyệt kỹ cua giai
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyThu Aug 23, 2012 5:36 am by Admin

» NETCAT.........
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyMon Aug 13, 2012 6:35 am by Admin

» Bảo mật CSDL bằng phương pháp mã hóa.
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyTue Apr 17, 2012 10:04 pm by Admin

» Hàm mã hóa MD5 bằng JavaScript
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyTue Apr 17, 2012 10:03 pm by Admin

» Giá của món quà
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyFri Apr 13, 2012 6:01 am by Admin

» Sẽ chỉ yêu ai?
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyFri Apr 13, 2012 6:01 am by Admin

» Cách đọc bảng chữ cái!
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyThu Apr 12, 2012 10:37 pm by Admin

» Gắn trojan, keylog, virus vào website, forum
Ứng dụng thuật toán DIJKSTRA tìm đường đi ngắn nhất EmptyTue Apr 10, 2012 1:14 am by Admin

Affiliates
free forum


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

Go down

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

Post  Admin 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
Admin

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

https://hackis.forumvi.com

Back to top Go down

Back to top

- Similar topics

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