dijkstra.c

这是个完整的c语言编写的dijkstra算法

/*
readme:
first,you need to input the node number, the cost matrix and the source node;
then the program will compute the best path.
finally,the program will output the lowest distance to the destination node, the pre-node and show the best path.
*/


#include <stdio.h>
#include <stdlib.h>
//Dijkstra算法实现函数
void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
	int i;
	int j;
	int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值
	int *s ;//定义具有最短路径的节点子集s
	s = (int *)malloc(sizeof(int) * n);
	//初始化最小路径代价和前一跳节点值
	for (i = 1; i <= n; i++)
	{
		dist[i] = cost[v][i];
		s[i] = 0;
		if (dist[i] == maxint)
		{
			prev[i] = 0;
		}
		else
		{
			prev[i] = v;
		}
	}
	dist[v] = 0;
	s[v] = 1;//源节点作为最初的s子集


	for (i = 1; i < n; i++)
	{
		int temp = maxint;
		int u = v;
		//加入具有最小代价的邻居节点到s子集
		for (j = 1; j <= n; j++)
		{
			if ((!s[j]) && (dist[j] < temp))
			{
				u = j;
				temp = dist[j];
			}
		}
		s[u] = 1;
		//计算加入新的节点后，更新路径使得其产生代价最短
		for (j = 1; j <= n; j++)
		{
			if ((!s[j]) && (cost[u][j] < maxint))
			{
				int newdist = dist[u] + cost[u][j];
				if (newdist < dist[j])
				{
					dist[j] = newdist;
					prev[j] = u;
				}
			}
		}
	}
}
//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{


	int j = 0;
	int w = u;
	int count = 0;
	int *way ;
	way=(int *)malloc(sizeof(int)*(n+1));
	//回溯路径
	while (w != v)
	{
		count++;
		way[count] = prev[w];
		w = prev[w];
	}
	//输出路径
	printf("the best path is:\n");
	for (j = count; j >= 1; j--)
	{
		printf("%d -> ",way[j]);
	}
	printf("%d\n",u);


}
//主函数，主要做输入输出工作
int main()
{
	int i,j,t;
	int n,v,u;

	int **cost;//代价矩阵
	int *dist;//最短路径代价
	int *prev;//前一跳节点空间


	printf("please input the node number: ");
	scanf("%d",&n);
	printf("please input the cost status:\n");

	cost=(int **)malloc(sizeof(int)*(n+1));


	for (i = 1; i <= n; i++)
	{
		cost[i]=(int *)malloc(sizeof(int)*(n+1));
	}
	//输入代价矩阵
	for (j = 1; j <= n; j++)
	{
		for (t = 1; t <= n; t++)
		{
			scanf("%d",&cost[j][t]);
		}
	}

	dist = (int *)malloc(sizeof(int)*n);
	prev = (int *)malloc(sizeof(int)*n);


	printf("please input the source node: ");
	scanf("%d",&v);
	//调用dijkstra算法  
	Dijkstra(n, v, dist, prev, cost);
	printf("*****************************\n");
	printf("have confirm the best path\n");
	printf("*****************************\n");
	for(i = 1; i <= n ; i++)
	{
		if(i!=v)
		{
			printf("the distance cost  from node %d to node %d is %d\n",v,i,dist[i]);
			printf("the pre-node of node %d is node %d \n",i,prev[i]);
			ShowPath(n,v,i, dist, prev);
		}
	}
	system("pause");
	return 0;
}