C语言实现Dijkstra算法（邻接矩阵与邻接表存储方式）

代码

#include <stdio.h>
#include <stdlib.h>
typedef int ArcType;
typedef char VerTextType[20];

#define MVNum 100 //顶点最大数
#define INF 0x3f3f3f3f

//图的邻接矩阵（Adjacency Matrix）表示
typedef struct
{
    VerTextType vexs[MVNum]; //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum; //顶点数
    int arcnum; //边数
} AMGraph; 


//图的邻接表存储
typedef struct ArcNode //边结点
{
    int adjver; //该边所指向的顶点位置
    struct ArcNode *nextarc; //指向下一条边的指针
    ArcType   weight;
} ArcNode;

typedef struct VNode //顶点信息
{
    VerTextType data;
    ArcNode     *firstarc;
} VNode, AdjList[MVNum];

typedef struct node
{
    AdjList vertices;
    int     vexnum; //图的当前顶点数
    int     arcnum; //图的当前边数
} ALGraph; 

//临接矩阵存储方式求最短路（dijkstra）,复杂度O(n^2)
//v0表示起点，D[i]表示从v0到i的最短路径长度，path存储路径
void ShortestPath_DIJ1(AMGraph G, int v0, ArcType D[], int Path[])
{
    int ok[MVNum], i, j; // ok数组标记是否确定最短路径
    for(i = 0; i < G.vexnum; i++) {
    	ok[i] = 0;
    	Path[i] = -1;
    	D[i] = INF;
    }
    D[v0] = 0;
    for(i = 0; i < G.vexnum; i++) {
    	int min_node = -1;
    	for(j = 0; j < G.vexnum; j++) {
    		if(ok[j] == 0 && (min_node == -1 || D[j] < D[min_node])) {
    			min_node = j;
    		}
    	}
    	if(min_node == -1) break;
    	ok[min_node] = 1;

    	for(j = 0; j < G.vexnum; j++) {
    		if(ok[j] == 0 && G.arcs[min_node][j] != 0 && D[j] > D[min_node] + G.arcs[min_node][j]){
    			D[j] = D[min_node] + G.arcs[min_node][j];
    			Path[j] = min_node;
    		}
    	}

    }

}

//临接表存储方式最短路径（dijkstra）,复杂度O(n^2)
void ShortestPath_DIJ2(ALGraph G, int v0, ArcType D[], int Path[])
{
    int ok[MVNum], i, j; // ok数组标记是否确定最短路径
    for(i = 0; i < G.vexnum; i++) {
    	ok[i] = 0;
    	Path[i] = -1;
    	D[i] = INF;
    }
    D[v0] = 0;
    for(i = 0; i < G.vexnum; i++) {
    	int min_node = -1;
    	for(j = 0; j < G.vexnum; j++) {
    		if(ok[j] == 0 && (min_node == -1 || D[j] < D[min_node])) {
    			min_node = j;
    		}
    	}
    	if(min_node == -1) break;
    	ok[min_node] = 1;

    	ArcNode * cur = G.vertices[min_node].firstarc;
    	while(cur != NULL) {
    		if(ok[cur -> adjver] == 0 && D[cur -> adjver] > D[min_node] + cur -> weight) {
    			D[cur -> adjver] = D[min_node] + cur -> weight;
    			Path[cur -> adjver]  = min_node;
    		}
    		cur = cur -> nextarc;
    	}
    }

}

//输入图
void init_graph(AMGraph *g1, ALGraph *g2) {
	int n,m;
	scanf("%d %d",&n,&m);  //输入顶点数和边数
	g1-> vexnum = g2-> vexnum = n;
	g1-> arcnum = g2-> arcnum = m;

	for(int i=0;i<MVNum;i++) for(int j=0;j<MVNum;j++) g1-> arcs[i][j]=0;
	for(int i=0;i<MVNum;i++) g2-> vertices[i].firstarc = NULL;

	for(int i=1;i<=m;i++) {
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		g1-> arcs[u][v] = w;

		ArcNode *cur = g2-> vertices[u].firstarc;
		if(cur == NULL) {
			g2-> vertices[u].firstarc = (ArcNode *) malloc(sizeof(ArcNode));
			g2-> vertices[u].firstarc -> adjver = v;
			g2-> vertices[u].firstarc -> weight = w;
			g2-> vertices[u].firstarc -> nextarc = NULL;
		}else{
			while(cur ->nextarc != NULL) {  //暴力处理，建议记录尾指针
				cur = cur -> nextarc;
			}
			cur -> nextarc = (ArcNode *) malloc(sizeof(ArcNode));
			cur = cur -> nextarc;
			cur -> adjver = v;
			cur -> weight = w;
			cur -> nextarc = NULL;
		}
	}
}

int main() {
	AMGraph g1;
	ALGraph g2;
	init_graph(&g1,&g2);
	int d1[MVNum],d2[MVNum],path1[MVNum],path2[MVNum];
	ShortestPath_DIJ1(g1,0,d1,path1);
	for(int i =0;i<g1.vexnum;i++) printf("%d ",path1[i]);
	printf("\n");
	ShortestPath_DIJ2(g2,0,d2,path2);
	for(int i =0;i<g2.vexnum;i++) printf("%d ",path2[i]);
	printf("\n");
}