苗火 Nicholas

[Data structures]Dijkstra

2019-7-30 萧 写技术

#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");
}

标签: Data Structures data_structures