求一个有向图中原点到其他各点的最短路径
不可达的路径值记为-1
邻接表存储
问题是无法完全输入所有的数据（最后一行）且输出错误
测试数据是：
6 11
1 2 50
1 3 10
1 5 45
2 3 15
2 5 10
3 1 20
3 4 15
4 2 20
4 5 35
5 4 30
6 4 3
应该输出：
1 3 10
1 4 25
1 2 45
1 5 45
1 6 -1
代码如下：
#include <stdio.h>
#include <stdlib.h>
#define MAX 10000
typedef struct edge//边点
{
int adjvex;
int weight;
struct edge *next;
}edge;
typedef struct node//顶点
{
int data;
edge*firstedge;
}node,adjlist[105];
typedef struct graph//图
{
int vn,en;
adjlist a;
}LGraph;
typedef struct path//路径相关信息
{
int visited[105];
int length[105];
}path;
LGraph* creategraph( )//建立图
{
LGraph*G=(LGraph*)malloc(sizeof(LGraph));
int vn,en;
scanf("%d %d\n",&vn,&en);
G->vn=vn;
G->en=en;
int i;
for(i=1;i<=vn;i++)//点集填充
{
int temp;
scanf("%d",&temp);
G->a[temp].data=temp;
G->a[temp].firstedge=NULL;
}
int j;
for(j=1;j<=en;j++)//边集填充
{
int v1,v2;
scanf("%d %d\n",&v1,&v2);
edge*p=(edge*)malloc(sizeof(edge));
p->adjvex=v2;
p->next=G->a[v1].firstedge;
G->a[v1].firstedge=p;
}
return G;
}
void InitPath(LGraph*G,path*dist)//对路径的一个初始化
{
dist->visited[1]=0;//问从源点开始的路径，标记为0，表示在集合S中
dist->length[1]=0;
int i;
for(i=2;i<=G->vn;i++)
{
dist->visited[i]=-1;
dist->length[i]=-1;
}
edge*p;
p=G->a[1].firstedge;
while(p)
{
dist->visited[p->adjvex]=1;
dist->length[p->adjvex]=p->weight;
p=p->next;
}
}
int Judge(LGraph*G,path*dist)//判断有没有归入集合S
{
int i;
for(i=1;i<=G->vn;i++)
{
if(dist->visited[i]==1)
{
return 1;
}
return 0;
}
}
//找到目前正在检索的点到它的右兄弟的最短的距离并返回该右兄弟的下标
int findminpath(LGraph*G,path*dist)
{
int minpath=MAX;
int minvex;
int i;
for(i=1;i<=G->vn;i++)
{
if(dist->visited[i]==1)
{
if(dist->length[i]<minpath)
{
minpath=dist->length[i];
minvex=i;
}
}
}
return minvex;
}
//更新路径,及对新加入S的这个minpath点的右兄弟进行遍历更新
void update(LGraph*G,path*dist,int minpath)
{
dist->visited[minpath]=0;
edge*p;
p=G->a[minpath].firstedge;
while(p)
{
if(dist->visited[p->adjvex]==1)
{
if(dist->length[minpath]+p->weight<dist->length[p->adjvex])
{
dist->length[p->adjvex]=dist->length[minpath]+p->weight;
}
}
else if(dist->visited[p->adjvex]==-1)
{
dist->visited[p->adjvex]=1;
dist->length[p->adjvex]=dist->length[minpath]+p->weight;
}
p=p->next;
}
}
void dijkstra(LGraph*G,path*dist)
{
InitPath(G,dist);
while(Judge(G,dist))
{
int min=findminpath(G,dist);
update(G,dist,min);
}
}
typedef struct reached
{
int re[105];
int data;
}reached;
reached*r;
int count=0;
void select(LGraph*G,path*dist)//先筛选出可以到达的结点，包括它的下标，路径值
{
int i;
for(i=1;i<=G->vn;i++)
{
if(dist->length[i]!=-1)
{
r->re[count]=dist->length[i];
r->data=i;
count++;
}
}
}
void bubblesort( )//冒泡排序
{
int swap=1;
int i;
for(i=count-1;i>=0&&swap==1;i--)//只要做要排序个数减一趟排序
{
swap=0;
int j;
for(j=0;j<=i;j++)//每一趟都两两排序
{
if(r->re[j]>r->re[j+1])
{
swap=1;
int temp=r->re[j];
r->re[j]=r->re[j+1];
r->re[j+1]=temp;
}
}
}
}
void print(LGraph*G,path*dist)
{
select(G,dist);
bubblesort( );
int i;
for(i=0;i<=count;i++)//先打印可连通的路径
{
printf("1 %d %d\n",r->data,r->re[i]);
}
int j;
for(j=1;i<=G->vn;j++)//再打印不可连通的，路径值也就是-1
{
if(dist->visited[j]==-1)
{
printf("1 %d %d\n",G->a[j].data,dist->length[j]);
}
}
}
int main()
{
LGraph*G;
path dist;
G=creategraph();
InitPath(G,&dist);
dijkstra(G,&dist);
print(G,&dist);
return 0;
}
