#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
typedef char DataType;
#define MaxVertices 10
#include "AdjLGraph.h"
void main()
{
int i,n,e,len,en,k,j,tt,f;int s[MaxVertices],t[MaxVertices];
int Row,Col,Wei;
int distance[MaxVertices];
int path[MaxVertices][MaxVertices];
AdjLGraph g;
struct Node *p,*q;
char v[MaxVertices];
AdjInitiate(&g);
printf("输入结点序列：");
scanf("%s",v);
len=strlen(v);
for(i=0;i<len;i++)
InsertVertex(&g,i,v[i]);
printf("输入边数：");
scanf("%d",&n);
printf("是否为有向图？是则输入1，否则输入2：");
scanf("%d",&en);
e=en*n;
printf("输入边的两结点和权值：\n");
for(i=0;i<e;i++)
{
scanf("%d,%d,%d",&Row,&Col,&Wei);
InsertEdge(&g,Row,Col,Wei);
}
printf("序号与结点：\n");
for(i=0;i<len;i++)
printf("(%d):%c\t",g.a[i].sorce,g.a[i].data);
printf("\n选择源点的序号：");
scanf("%d",&k);
for(i=0;i<len;i++)
{
distance[i]=0;
}
for(i=0;i<MaxVertices;i++)
{ for(j=0;j<MaxVertices;j++)
path[i][j]=-1;
}
for(i=0;i<MaxVertices;i++)
{
s[i]=0;
t[i]=0;
}
q=g.a[k].adj;
while(q!=NULL)
{
distance[q->dest]=q->weight;
path[q->dest][0]=k;
path[q->dest][1]=q->dest;
q=q->next;
}
s[k]=1;
while(!condition(s,len))
{
tt=MinDis(distance,s,len);
j=0;
p=g.a[tt].adj;
while(p!=NULL&&distance[tt]!=0)
{
if(distance[p->dest]>distance[tt]+p->weight||distance[p->dest]==0)
{
distance[p->dest]=distance[tt]+p->weight;
j=0;
while(path[tt][j]!=-1)
{
path[p->dest][j]=path[tt][j];
j++;
}
path[p->dest][j]=p->dest;
for(i=j+1;i<MaxVertices;i++)
path[p->dest][i]=-1;
}
p=p->next;
}
s[tt]=1;
}
t[k]=1;
while(!condition(t,len))
{
j=0;
f=MinDis(distance,t,len);
t[f]=1;
printf("\n最短距离\t%d",distance[f]);
printf("\t");
while(path[f][j]!=-1)
{
printf("%c-->",g.a[path[f][j]].data);
j++;
}
printf("\b\b\b ");
}
printf("\n");
}
