迪杰斯特拉算法（邻接表求解）

[基本思想]

1. 与邻接矩阵表示的方法不同的是，在更新dis数组和path数组时，只需要把求u到j距离的g.edges[u][j]换成邻接表表示
2. g.edges[u][j]表示u到j的距离，因此可以写一个getWeight(g, u, j)算法用于计算u到j的距离

[核心函数]

//获得边的权重
float getWeight(AGraph *G, int u, int j)
{
	ArcNode *p = G->adjlist[u].firstarc;
	while(p != NULL)
	{
		if(p->adjvex == j)
			return p->weight;
		p = p->nextarc;
	}
	return INF;
}

[数据]

8 13
0 1 6
0 3 1
0 5 50
1 3 11
1 2 43
1 4 6
2 7 8
3 4 12
4 2 38
4 6 24
5 4 1
5 6 12
6 7 20

[完整代码]

#include<stdio.h>
#include<stdlib.h>
#define MAXVEX 100
#define maxSize 100
#define INF 99999

typedef struct ArcNode
{
	int weight;		//记录权值
	int adjvex;		//邻接点
	struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
	int data;
	ArcNode *firstarc;
}VNode;
typedef struct AGraph
{
	VNode adjlist[MAXVEX];
	int numNodes, numEdges;
}AGraph;

//创建图
void CreateGraph(AGraph *G)
{
	int i;
	int m, n, weight;

	FILE *fp = fopen("data.txt", "r");
	fscanf(fp, "%d %d", &G->numNodes, &G->numEdges);

	for(i = 0; i < G->numNodes;i++)
		G->adjlist[i].firstarc = NULL;

	for(i = 0; i < G->numEdges;i++)
	{
		fscanf(fp, "%d %d %d", &m, &n, &weight);
		ArcNode *pe = (ArcNode *)malloc(sizeof(ArcNode));
		pe->adjvex = n;
		pe->weight = weight;
		pe->nextarc = G->adjlist[m].firstarc;
		G->adjlist[m].firstarc = pe;

		//ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
		//p->adjvex = n;
		//p->weight = weight;
		//p->nextarc = G->adjlist[m].firstarc;
		//G->adjlist[m].firstarc = p;
	}

	fclose(fp);

}

//获得边的权重
float getWeight(AGraph *G, int u, int j)
{
	ArcNode *p = G->adjlist[u].firstarc;
	while(p != NULL)
	{
		if(p->adjvex == j)
			return p->weight;
		p = p->nextarc;
	}
	return INF;
}

//迪杰斯特拉算法
void Dijkstra(AGraph *G, int dist[], int path[], int v)
{
	int set[maxSize];
	int i, j, u, min;
	float weight;
	//给三个数组赋初值
	for(i = 0;i < G->numNodes; i++)
	{
		set[i] = 0;
		path[i] = -1;
		dist[i] = INF;
	}

	ArcNode *p = G->adjlist[v].firstarc;
	while(p != NULL)
	{
		dist[p->adjvex] = p->weight;
		path[p->adjvex] = v;
		p = p->nextarc;
	}
	path[v] = -1;
	set[v] = 1;
	dist[v] = 0;

	for(i = 0;i < G->numNodes - 1;i++)
	{
		min = INF;

		for(j=0;j < G->numNodes;j++)
		{
			if(set[j] == 0 && dist[j] < min)
			{
				min = dist[j];
				u = j;
			}
		}
		set[u] = 1;

		for(j=0;j < G->numNodes;j++)
		{
			float weight = getWeight(G, u, j);
			if(set[j] == 0 && dist[u] + weight < dist[j])
			{
				dist[j] = dist[u] + weight;
				path[j] = u;
			}
		}
	}
}

//输出路径
void print_path(int path[], int v1)
{
	if(path[v1]==-1)
		printf("%d ", v1);
	else
	{
		print_path(path, path[v1]);
		printf("%d ", v1);
	}
}

int main()
{
	AGraph *G = (AGraph *)malloc(sizeof(AGraph));
	int v, v1;

	CreateGraph(G);

	int *path = (int *)malloc(sizeof(int)*G->numNodes);
	int *dist = (int *)malloc(sizeof(int)*G->numNodes);

	printf("输入起始点: ");
	scanf("%d", &v);

	printf("输入终止点: ");
	scanf("%d", &v1);

	Dijkstra(G, dist, path, v);
	
	printf("最短路径为: ");
	print_path(path, v1);

	getchar();
	getchar();
	return 0;
}