我改了后还是不能正确输出
我的程序：
#include <iostream.h>
const int INF=65536;
const int MAX=5;
int c[5][5]={{0 ,10 ,INF,30 ,100},
{INF,0 ,50 ,INF,INF},
{INF,INF,0 ,INF,10},
{INF,INF,20 ,0 ,60},
{INF,INF,INF,INF,0}};
void Dijkstra(int n,int v);
int main()
{
int n=5,v=0;
// int dist[MAX],prev[MAX];
Dijkstra(n,v);
return 0;
}
void Dijkstra(int n,int v)
{
int dist[MAX],
prev[MAX];
bool s[MAX];
int i,j,newdist;
for(i=0;i<n;i++)
{
dist[i]=c[v][i];
s[i]=false;
if(dist[i] == INF)prev[i]=-1;
else prev[i]=v;
}
dist[v]=0;s[v]=true;
for(i=0;i<n;i++)
{
int temp=INF;
int u=v;
for(j=0;j<n;j++)
{
if((!s[j]) && (dist[j]<temp))
{
u=j;
temp=dist[j];
}
}
s[u]=true;
// int newdist;
for(j=0;j<n;j++)
{
if((!s[j]) && (c[u][j]<INF))
{
newdist=dist[u]+c[u][j];
}
if(newdist<dist[j])
{
dist[j]=newdist;
prev[j]=u;
}
}
}
for(i=0;i<5;i++)
cout<<dist[i]<<"\t";
cout<<endl;
for(j=0;j<5;j++)
cout<<prev[j]<<"\t";
cout<<endl;
}
下面是我们老师给的程序：
#include<iostream.h>
const int INF=65536; //无穷大
const int MAXV=6;
int graph[MAXV][MAXV]={{INF, 1, 12,INF,INF,INF}, //有向图的邻接矩阵表示
{INF,INF, 9, 3,INF,INF},
{INF,INF,INF,INF, 5,INF},
{INF,INF, 4,INF,13, 15},
{INF,INF,INF,INF,INF,4},
{INF,INF,INF,INF,INF,INF}};
//输出最短路径的中间的各顶点
void ppath(int path[],int i,int v0)
{
int k;
k=path[i];
if(k==v0) return;
ppath(path,k,v0);
cout<<"V"<<k<<"→";
}
//输出从源点到每一个可达点的距离
void PrintPath(int dis[],int path[],int s[],int n,int v0)
{
int i;
for(i=1;i<n;i++)
{
if(s[i]==1)
{
cout<<"从V"<<v0<<"到V"<<i<<"的最短路径长度为:"<<dis[i];
cout<<"，路径是：V"<<v0<<"→"; //起点
ppath(path,i,v0); //中间的各顶点
cout<<"V"<<i<<endl; //终点
}else{
cout<<"从V"<<v0<<"到V"<<i<<"的路径不存在\n";
}
}
}
void Dijkstra(int n,int v0) //n为顶点个数,v0为源点
{
int dis[MAXV], //dis[i]保存从源点到终点vi目前最短路径的长度
path[MAXV]; //path[i]保存从源点v0到终点vi当前最短路径中前一个顶点的编号
int s[MAXV]; //已找到时最短路径的点
int mindis,i,j,u;
for(i=0;i<n;i++) //距离初始化
{
dis[i]=graph[v0][i];
s[i]=0;
if(graph[v0][i]<INF){
path[i]=v0;
}else{
path[i]=-1;
}
}
s[v0]=1;
path[v0]=0;
for(i=0;i<n;i++)
{
//选取不在S中且有最小距离的顶点u
mindis=INF;
u=-1;
for(j=0;j<n;j++){
if(s[j]==0&&dis[j]<mindis)
{
u=j;
mindis=dis[j];
}
}
s[u]=1;
//修改不在S中的顶点的距离
for(j=0;j<n;j++){
if(s[j]==0){
if(graph[u][j]<INF&&dis[u]+graph[u][j]<dis[j]){
dis[j]=dis[u]+graph[u][j];
path[j]=u;
}
}
}
}
//输出最短路径
PrintPath(dis,path,s,n,v0);
}
void main()
{
Dijkstra(6,0);
}
///////////////
大家看看我的程序出在哪儿啊
再问下,箭头怎么输出的，还有斜向上的箭头呢
