#include <stdio.h>
#include <stdlib.h>
#define MAX 20
#define INFINIT 65535
typedef struct _MGraph{
char vexs[MAX];
int arcs[MAX][MAX];
int vexnum;
int arcnum;
}MGraph;
int visited[MAX];
int LocateVex(MGraph *G, char v)
{
int i=0;
while(i<G->vexnum && G->vexs[i] != v){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
int CreateDN(MGraph *G)
{
int i,j,k;
char v1,v2;
int cost;
scanf(" %d %d", &G->vexnum, &G->arcnum);
for(i=0; i<G->vexnum; i++){
scanf(" %c", &G->vexs[i] );
}
for(i=0; i<G->vexnum; i++){
for(j=0; j<G->vexnum; j++){
if(i==j){
G->arcs[i][j] = 0;
}else{
G->arcs[i][j] = INFINIT;
}
}
}
for(k=0; k<G->arcnum; k++){
scanf(" %c %c %d", &v1, &v2, &cost);
i=LocateVex(G, v1);
j=LocateVex(G, v2);
G->arcs[i][j] = cost;
}
return 1;
}
int FirstAdjvex(MGraph *G, int v)
{
int i=0;
while(i<G->vexnum && G->arcs[v][i] == INFINIT){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
int NextAdjvex(MGraph *G, int v, int w)
{
int i=w+1;
while(i<G->vexnum && G->arcs[v][i] == INFINIT){
i++;
}
if(i<G->vexnum){
return i;
}else{
return -1;
}
}
void Dijkstra(MGraph *G, int v0, int (*P)[MAX], int *D)
{
int i;
int j;
int k;
int min;
int v;
int w;
int visited[MAX];
for(i=0; i<G->vexnum; i++){
D[i] = G->arcs[v0][i]; //v0->i
for(j=0; j<G->vexnum; j++){
P[i][j] = 0; //v0->j->i
}
if(D[i] < INFINIT){
P[i][v0] = 1; //v0->v0->i
P[i][i] = 1; //v0->i->i
}
visited[i] = 0;
}
D[v0] = 0;
v = v0;
visited[v0] = 1;
for(i=1; i<G->vexnum; i++){
min = INFINIT;
for(j=0; j<G->vexnum; j++){
if(!visited[j]){
if(min>D[j]){
min = D[j];
v = j;
}
}
}
visited[v]=1;
for(j=0; j<G->vexnum; j++){
if(!visited[j] && D[j] > D[v] + G->arcs[v][j]){
D[j] = D[v] + G->arcs[v][j];
for(k=0; k<G->vexnum; k++){
P[j][k] = P[v][k] || P[j][k];
}
P[j][v] = 1;
}
}
}
}
void main()
{
MGraph G;
int P[MAX][MAX];
int D[MAX];
int i,j;
printf("log.anycle.com\n\n");
printf("Create graph:\n");
CreateDN(&G);
for(i=0; i<G.vexnum; i++){
for(j=0; j<G.vexnum; j++){
printf(" %5d", G.arcs[i][j]);
}
printf("\n");
}
printf("\n");
printf("Dijkstra:\n");
Dijkstra(&G, 0, P, D);
for(i=0; i<G.vexnum; i++){
printf(" %c", G.vexs[i]);
}
printf("\n");
for(i=0; i<G.vexnum; i++){
printf(" %5d(", D[i]);
for(j=0; j<G.vexnum; j++){
if(P[i][j]){
printf("%c", G.vexs[j]);
}else{
printf(" ");
}
}
printf(")");
}
printf("\n");
}