dijkstra.cpp

来自「dijkstra算法的链表实现,另外需要include一个头文件,稍后上传」· C++ 代码 · 共 166 行

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

float adjacent[MAX][MAX];
int link[MAX*2];
float condition[MAX];
int node_num;

int found(int node);
float shortcircuit(int *lastnode,int i);
void show_path(int i,int source_P);
int non_left();
int getback(int i);

void main()
{
	int i = 0,j,flag = 0,source_P,lastnode = -1,k=0;
	float least,temp1,temp2;
	char c = ' ';
	printf("Input the number of nodes.\n");
	scanf("%d",&node_num);
	for(i=0;i < node_num-1;i++)
		for(j=i+1;j< node_num ;j++)
		{
			printf("输入节点 %d 和节点 &d 之间路的权(用 -1 表示没有边连接):\n",i+1,j+1);
			scanf("%f",&adjacent[i][j]);
		}
	for(i = 0;i < node_num - 1;i++)
	{
		for(j = i + 1;j < node_num;j++)
			adjacent[j][i]=adjacent[i][j];
	
	}
	for(i=0;i<node_num;i++)
		adjacent[i][i] =0;
	printf("输入源点 P 的编号:\n");
	scanf("%d",&source_P);
	while(source_P > node_num || source_P <= 0)
	{
		printf("超出范围，重新输入:\n");
		scanf("%d",&source_P);
	}
	source_P--;
	for(i = 0;i < node_num;i++)
		condition[i]=(i == source_P)?0:(-1);
	flag=0;
	while(!non_left())                                                            
	{
		for(i = 0;i < node_num;i++)
			if(!found(i))
			{
				temp1 = temp2;
				if((temp2 = shortcircuit(&lastnode,i)) == -2)
					temp2 = temp1;
				if(flag)
					temp2 = (temp1 < temp2) ? temp1 : temp2;
				if(shortcircuit(&lastnode,i) != -2)
					flag = 1;
			}
		if(flag)
		{
			least = temp2;
			flag = 0;
			for(j = 0;j < node_num;j++)
			{
				if(shortcircuit(&lastnode,j) == least)
				{
					condition[j] = least;
					if(lastnode != -1)
					{
						link[k++]=lastnode;
						link[k++]=j;
					}
				}
			}
		}
	}
	for(i = 0;i < node_num;i++)
		if(i != source_P)
		{
			if(condition[i] != -1)
			{
				printf("节点 %d 和节点 %d 之间的最短路径长度是: %g.\n",source_P + 1,i + 1,condition[i]);
				show_path(i,source_P);
			}
			else
				printf("节点 %d 和节点 %d 是不连通的.\n",source_P + 1,i + 1);
		}
}

int found(int node)
{
	return((int)condition[node] >= 0);
}

float shortcircuit(int *lastnode,int i)
{
	int j,flag = 0;
	float temp1,temp2 = -2;
	*lastnode=-1;
	for(j = 0;j < node_num;j++)
		if(found(j))
			if((int)adjacent[i][j] != -1)
			{
				temp1 = temp2;
				temp2 = adjacent[i][j] + condition[j];
				if(flag)
				{
					if (temp2 < temp1)
						*lastnode = j;
					temp2 = (temp1 < temp2) ? temp1 : temp2;
				}
				else
					*lastnode = j;
				flag = 1;
			}

	return temp2;
}

int non_left()
{
	int i,flag = 0,lastnode;
	for(i = 0;i < node_num;i++)
		if(!(found(i)))
			if((int)shortcircuit(&lastnode,i) != -2)
			{
				flag = 1;
				break;
			}
			return !flag;
}

void show_path(int i,int source_P)
{

	int j = i,k=0;
	int circuit[MAX];
	circuit[k++]=j;
	while(getback(j) != source_P)
	{
		circuit[k++]=getback(j);
		j = getback(j);
	}
	printf("  最短路是: %d",source_P + 1);
	for(j = k-1;circuit[j]!=i;j--)
		printf(" -> %d",circuit[j] + 1);
	printf(" -> %d\n",i + 1);


}

int getback(int i)
{
	int position;
	for(position = 1;;position += 2)
	{
		if(link[position] == i)
			break;
	}
	return link[position - 1];
}