#include<iostream.h>
#include<conio.h>
#include<graphics.h>
#include<stdlib.h>
#include<math.h>
#include<stdio.h>
#define TOIDA 50
#define VOCUNG 30000
#define TRUE 1
#define FALSE 0
/* Khai bao ma tran trong so cua do thi
trongso[i][j] = VOCUNG: neu tren do thi khong co cung <i, j>
trongso[i][j] != 0 : tren do thi co cung <i, j> */
class NUT
{
private :
int x,y;
public :
void nhap();
void hien();
void ve_dinh()
{
putpixel(x,y,15);
}
void ve_dt(NUT d2,int mau)
{
setcolor(mau);
line(this->x,this->y,d2.x,d2.y);
}
};
class DOTHI
{
private:
int SoNut; // so nut thuc su co tren do thi
NUT *nut; //kbao con tro *nut-tra ve kieu NUT
int trongso[TOIDA][TOIDA];//kbao mang chua trong so
public:
void nhap();
void kdongMT();
void duongngan1();
void dijkstra(int s, int t, int *ngan1, int duongdi[]);
void ve();
};
// Khoi dong ma tran trong so cua do thi
void DOTHI::kdongMT()
{
int i, j;
for(i = 0; i < TOIDA; i++)
for(j = 0; j < TOIDA; j++)
trongso[i][j] = VOCUNG;
}
void NUT::nhap()
{
}
void DOTHI::nhap()
{ int x,y,wt;
cout<<"Do thi co bao nhieu nut :"<<endl
; cout<<"\nHay nhap cac cung cua do thi (Nhap "<<SoNut
<<" "<<SoNut
<<"de ket thuc:"<<endl
; x=0;
y=0;
while(x<=SoNut && y<=SoNut)
{
if(x<=SoNut && y<=SoNut)
{
cout<<"Trong so cua cung"<<x
<<" "<<y
<<":";cin>>wt
; trongso[x][y]=wt;
}
};
}
void DOTHI::ve()
{ for(int i=1;i<SoNut;i++)
nut[i].ve_dt(nut[i+1],14);
nut[1].ve_dt(nut[SoNut],14);
}
void ktdh() //Ham khoi tao do hoa
{ int gm=0,gd=0;
initgraph(&gm,&gd,"..\\bgi");
if(graphresult()!=0)
{ cout<<"Loi do hoa!"; getch
(); exit(1); }
}
/* Ham dijkstra: tim duong di ngan nhat tren do thi co trong so theo
giai thuat Dijkstra.
Du lieu nhap:
s: nut di, t: nut den
Du lieu xuat:
ngan1: chieu dai duong di ngan nhat tu s den t
duongdi[]: mang ghi nhan lo trinh ngan nhat tu s den t, luu y
duongdi[i] la nut truoc nut i tren lo trinh ngan nhat */
void DOTHI:: dijkstra(int s, int t, int *ngan1, int duongdi[])
{
int i, k, kc, nuthientai, min, kcachmoi;
int tapcacnut[TOIDA]; // tap cac nut da xet
int kcach[TOIDA]; /* mang luu chieu dai duong di ngan nhat tu nut
s den cac nut khac */
// Buoc 0: khoi dong mang tapcacnut[] va kcach[]
for(i = 0; i < SoNut; i++)
{
tapcacnut[i] = FALSE;
kcach[i] = VOCUNG;
}
// dua nut s vao tap nut da xet
tapcacnut[s] = TRUE;
kcach[s] = 0;
nuthientai = s;
/* vong lap thuc hien cac buoc 1, 2, ... cho den khi dua duoc nut t vao
tap nut da xet */
while(nuthientai != t)
{
min = VOCUNG;
kc = kcach[nuthientai]; /* kc chieu dai duong di ngan nhat tu nut s
den nuthientai */
for(i = 0; i < SoNut; i++)
if(tapcacnut[i] == FALSE)
{
kcachmoi = kc + trongso[nuthientai][i];
if(kcachmoi < kcach[i])
{
kcach[i] = kcachmoi;
duongdi[i] = nuthientai; /* gan nuthientai la nut truoc
nut i tren lo trinh */
}
if(kcach[i] < min)
{
min = kcach[i];
k = i;
}
}
// Dua nut k vao tap nut da xet
nuthientai = k;
tapcacnut[nuthientai] = TRUE;
}
*ngan1 = kcach[t];
}
void DOTHI::duongngan1()
{ int s,t,i;
int ngan1;
int duongdi[TOIDA];
dijkstra(s,t,&ngan1,duongdi);
cout<<"Duong di ngan nhat tu"<<s
<<"->"<<t
<<"la "<<ngan1
; i=t;
while(i!=s)
{
i=duongdi[i];
}
}
void main()
{ clrscr();
DOTHI dothi;
dothi.nhap();
dothi.kdongMT();
dothi.duongngan1();
ktdh();
dothi.ve();
getch();