c#实现最短路径算法

发布网友发布时间：2022-05-15 18:48

共1个回答

热心网友时间：2024-02-26 23:12

oo
{
int len,num;
struct oo *next;
} link;

typedef struct
{
int num;
link *next;
} graph;

/*
node[]图的邻接表
n节点总数
s源点
dis[]到源点的最短路径长度
pre[]最短路径上的前驱结点
算法返回true，当且仅当途中不包含从源点可达的负权回路
*/

bool bellmanFord(graph node[],int n,int s)
{
int dis[MAX],pre[MAX];
int i,j;
link *p;
for(i=0;i<n;i++)
{
dis[i]=MAXVALUE;
pre[i]=-1;
}
dis[s]=0;
for(i=0;i<n;i++)
{
p=node[i].next;
while(p)
{
if(p->len+dis[i]<dis[p->num])

p=p->next;
}
p=node[i].next;
while(p)
{
if(p->len+dis[i]<dis[p->num])
return false;
p=p->next;
}
}
for(i=0;i<n;i++)
{
printf("%d %d\n",i,dis[i]);
j=i;
while(j!=-1)
{
printf("%d ",j);
j=pre[j];
}
cout<<endl;
}
return true;
}

//这个是邻接矩阵
const int MAX = 100;
const int MAXVALUE = 1000;

int graph[MAX][MAX],n;
/*
graph[][]图的邻接阵
n 图的节点数
s 源点
dis[] 存放最短路径
pre[] 存放最短路径上的前驱节点
算法返回true，当且仅当途中不包含从源点可达的负权回路，并输出每个节点最短路径的前驱值
*/

bool bellmanFord(int graph[][MAX],int n,int s)
{
int dis[MAX],pre[MAX];
int i,j,k;
for(i=0;i<n;i++)
{
dis[i]=MAXVALUE;
pre[i]=-1;
}
dis[s]=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
if(i!=j&&dis[j]>dis[i]+graph[i][j])
{
dis[j]=dis[i]+graph[i][j];
pre[j]=i;
}
for(j=0;j<n;j++)
if(i!=j&&dis[j]>dis[i]+graph[i][j])
return false;
}
for(i=0;i<n;i++)
{
printf("%d %d\n",i,dis[i]);
k=i;
while(pre[k]!=-1)
{
printf("%d ",pre[k]);
k=pre[k];
}
cout<<endl;
}
return true;
}