Giúp em về thuật toán Dijkstra & Bellman!!!

[tabh]

Em đang làm 2 thuật toán trên nhưng test vẫn còn sai.Có anh chị nào biết có thể giúp em thuật toán đúng nhất không? Bài làm của em theo kiểu đọc file .dat ở ngoài và đưa vào mảng.

[hiepsi4rum]

đây là phần coding của thuật toán Dijkstra, còn phần input và output từ file thì bạn có thể tự làm bình thường!!! Còn về thuật toán Bellman thì mình chưa từng nghe, ai biết thì làm ơn post lẹn giùm nha!!
#include<iostream.h>
#include<conio.h>
#include<values.h>
#define max 50
int n,s,t;
char ch;
typedef long GRAPH[max][max];
GRAPH c;
int befor[max], final[max], d[max];

void init(GRAPH &c)
{
int i,j;
cout<<" Given number of vertices of graph n="; cin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
cout<<"c["<<i<<","<<j<<"]="; cin>>c[i][j];
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) if(c[i][j]==0) c[i][j]=MAXINT;
}
void print_data(GRAPH c)
{
int i,j;
cout<<"Distnce matrix\n";
for(i=1;i<=n; i++)
{
for(j=1;j<=n;j++) cout<<c[i][j]<<" ";
cout<<"\n";
}
}
void result(int s,int t)
{
int i,j;
cout<<"The shortest path from "<<s<<" to "<<t<<"\n";
cout<<t<<"<=";
i=befor[t];
while(i!=s)
{
cout<<i<<"<=";
i=befor[i];
}
cout<<s<<endl;
cout<<"The length of shortest path is:"<<d[t];
getch();
}
void dijkstra(GRAPH c, int & s, int &t)
{
int v,u,minp;
for(v=1;v<=n;v++)
{
d[v]=c[s][v];
befor[v]=s;
final[v]=0;
}
befor[s]=0;
d[s]=0;
final[s]=1;
while(!final[t])
{
// finding u such that d[u] is minimal (Extract_Min(Q)
minp=MAXINT;
for(v=1;v<=n;v++)
if(!final[v]&&minp>d[v])
{
u=v;
minp=d[v];
}
final[u]=1;
if(!final[t])
for(v=1;v<=n;v++)
if((!final[v])&&(d[v]>d[u]+c[u][v]))
{
d[v]=d[u]+c[u][v];
befor[v]=u;
}
}
}
void menu()
{
clrscr();
cout<<"PROGRAM SEARCHS THE SHORTEST PATH FROM S TO ALL VERTICES OF GRAPH\n";
cout<<" FOLLOWING ALGORITHM OF DIJKSTRA\n";
cout<<" **********************************\n";
cout<<" 1. Input from keyboard\n";
cout<<" 2. Solution of problem\n";
cout<<" ESC. Exit\n";
cout<<"-----------------------------------------------------------------\n";
cout<<" Select a task: ";
}

void main()
{
clrscr();
do{
menu();
ch=getch();
cout<<ch<<"\n";
switch(ch){
case '1':init(c); break;
case '2': {
print_data(c);
cout<<"Start and final vertex: "; cin>>s>>t;
dijkstra(c,s,t);
result(s,t);
break;
}
}
} while (ch!=27);
}

[HoangNhat]

source Bellman viết bằng Oop:
#include<conio.h>
#include<iostream.h>
#include<values.h>
#include<stdio.h>
#include<stdlib.h>
//=-=-=-=-=-=-=-=-=-=
#define max 100
#define vc MAXINT
//=-=-=-=-=-=-=-=-=-=
class Graph{
public:
Graph(){k=1;}
void input(char*);
void output(char*);
void Bellman();
private:
int L[max][max];
int P[max][max];
int nVer;
int min;
int k;
int DinhTruoc[max];
};
//=-=-=-=-=-=-=-=-=-=
//=-=-=-=-=-=-=-=-=-=
void Graph::input(char* filename)
{
FILE* f;
f=fopen(filename,"r");
if(f==NULL)
{
cerr<<"Can't read this file.\n";
exit(1);
}
else
fscanf(f,"%d",&nVer);
for(int i=0;i<nVer;i++)
for(int j=0;j<nVer;j++)
fscanf(f,"%d",&L[i][j]);
fclose(f);
}
//=-=-=-=-=-=-=-=-=-=
void Graph::output(char* filename)
{
FILE* f;
f=fopen(filename,"wr");
fprintf(f,"Duong di ngan nhat sau khi dung thuat toan Bellman.\n");
for(int j=0;j<nVer;j++)
fprintf(f,"%d\t",P[k][j]);
fprintf(f,"\nDuong di ngan nhat.\n");
fclose(f);
}
//=-=-=-=-=-=-=-=-=-=
void Graph::Bellman()
{
for(int i=0;i<nVer;i++)
{
P[0][i]=vc;
DinhTruoc[i]=-1;
}
P[0][0]=0;
int flag,v;
while(k<=nVer&&flag)
{
flag=0;
for(int i=0;i<nVer;i++)
{
v=-1;
min=P[k-1][i];
for(int j=0;j<nVer;j++)
{
if((P[k-1][j]!=vc)&&(L[j][i]!=0))
if(P[k-1][j]+L[j][i]<min)
{
min=P[k-1][j]+L[j][i];
flag=1;
v=j;
}
}
P[k][i]=min;
if(v!=-1)
DinhTruoc[i]=v;
}

if(flag) k++;
}
if (k>nVer)
cout<<"\nDo thi co mach am.\n";
else
cout<<"\nDo thi khong co mach am.\n";
}
//=-=-=-=-=-=-=-=-=-=
void main()
{
clrscr();
Graph g;
g.input("c:\\working\\bellman.inp");
g.Bellman();
g.output("c:\\working\\bellman.out");
getch();
}

[hechay]

phương pháp chủ đạo là quy hoạch động đó bạn . mình ko biết c mà chỉ biết pascal thôi nên không giúp bạn được nhiều . các bước là lập bảng đường đi , so sánh , đi ngược . chừng đó là xong 2 cái Dijkstra,Bellman rồi .

[tritai]

có thuật toán viết bằng c++ không, mới học nên hổng biết gì hết, giúp mình với