博客

#include<stdio.h>
#include<stdlib.h>
#define maxsize 100
#define INFINITY 65535
typedef int InfoType;
typedef int VexType;
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	InfoType info;
}ArcNode;
typedef struct VNode{
	VexType data;
	ArcNode *firstarc;
}VNode,AdjList[maxsize];
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
	int kind;
}AGraph; 

int locate(AGraph *G,VexType vex){
	int i;
	for(i=0;i<G->vexnum;i++){
		if(G->vertices[i].data==vex)
			return i;
	}
	return -1;
}

AGraph *creat()
{
    AGraph *G=(AGraph*)malloc(sizeof(AGraph));
    printf("请输入顶点数目：");
    scanf("%d", &(G->vexnum));
    printf("请输入弧的数目：");
    scanf("%d", &(G->arcnum));
     
    int i,k;
    VexType vex;
    VexType v1, v2,info;
    printf("请输入顶点信息：\n");
    for (i = 0; i < G->vexnum; i++)
    {
        scanf("%d", &vex);
        G->vertices[i].data = vex;
        G->vertices[i].firstarc = NULL;
    }
    
    printf("请输入弧的信息：\n");
    for (k = 0; k < G->arcnum; k++)
    {
    	scanf("%d%d%d", &v1, &v2,&info);  
        int a = locate(G, v1);      
        int b = locate(G, v2);      
    
        ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = b;p->info=info;
        p->nextarc = G->vertices[a].firstarc;
        G->vertices[a].firstarc = p;
    }
    return G;
}

int sortP(int dist[],int n,int set[]){
	int k=0,min,i;
	while(set[k]==1) k++;
	min=dist[k];
	for(i=k+1;i<n;i++){
		if(set[i]==0&&dist[i]<min){
			k=i;min=dist[i];
		}
	}
	return k;
}

void ShortestPath(AGraph *G,int v0){
	int n=G->vexnum;
	int dist[n],path[n],set[n];
	ArcNode *p;
	int vl=locate(G,v0),i;
	for(i=0;i<n;i++){
		dist[i]=INFINITY;
		path[i]=-1;
		set[i]=0;
	}
	for(p=G->vertices[vl].firstarc;p;p=p->nextarc){
		dist[p->adjvex]=p->info;
		path[p->adjvex]=vl;
	}
	set[vl]=1;
	int k,min,m;
	for(i=0;i<n-1;i++){
		min=sortP(dist,n,set);
		set[min]=1;
		
		for(p=G->vertices[min].firstarc;p;p=p->nextarc){
			m=p->adjvex;
			if(set[m]==0&&dist[m]>dist[min]+p->info){
				dist[m]=dist[min]+p->info;
				path[m]=min;
			}
		}
	}
	
	for(i=0;i<n;i++){
		printf("%d %d %d\n",set[i],dist[i],path[i]);
	}
} 


int main(){
	AGraph *G=creat();
	ShortestPath(G,0);
	return 0;
}

输入：
请输入顶点数目：7
请输入弧的数目：12
请输入顶点信息：
0 1 2 3 4 5 6
请输入弧的信息：
0 1 4 0 2 6 0 3 6 1 2 1 3 2 2 1 4 7 3 5 5 2 4 6 2 5 4 5 4 1 4 6 6 5 6 8

输出：
1 65535 -1
1 4 0
1 5 1
1 6 0
1 10 5
1 9 2