首页 > 代码库 > 好记的迪杰斯特拉算法

好记的迪杰斯特拉算法

2024-07-17 10:05:43   224人阅读

好记的迪杰斯特拉算法

核心代码

       不包括花括号的话10行代码.set[]代表顶点集合S，算法的核心思想就是不断根据贪心算法把距离集合S最近的顶点加到集合中.
dis则是距离，源点离各结点的距离.
	for(i=1;i<N;i++)
	{
		Min=65535;		
		for(j=0;j<N;j++)
		{
			if(!set[j]&&dis[j]<Min)
			{
				k=j;
				Min=dis[j];
			}
		}
		set[k]=1;		
		for(j=0;j<N;j++)
		{
			if(!set[j]&&(Min+arc[k][j]<dis[j]))
				dis[j]=Min+arc[k][j];
		}
	}

记下上面的代码后，我们要做的就是倆个初始化，一个是图的初始化

const int N=9,INF=65535;
int vexs[N];
int arc[N][N];

void init()
{
	//初始化图
	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[i][j] =INF;
		}
	}
	arc[0][1]=1;
	arc[0][2]=5; 
	arc[1][2]=3; 
	arc[1][3]=7; 
	arc[1][4]=5; 

	arc[2][4]=1; 
	arc[2][5]=7; 
	arc[3][4]=2; 
	arc[3][6]=3; 
	arc[4][5]=3;

	arc[4][6]=6;
	arc[4][7]=9; 
	arc[5][7]=5; 
	arc[6][7]=2; 
	arc[6][8]=7;

	arc[7][8]=4;

	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[j][i] =arc[i][j];
		}
	}
	for(int i=0;i<N;i++)
		vexs[i]=i;
}

迪杰斯特拉算法的初始化，即选定源节点.

//初始化(这里以V0点开始)
for(i=0;i<N;i++)
{
	set[i]=0;
	dis[i]=arc[0][i];
}
dis[0]=0;
set[0]=1;

给出完整的代码

#include<stdio.h>
const int N=9,INF=65535;
int vexs[N];
int arc[N][N];

void init()
{
	//初始化图
	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[i][j] =INF;
		}
	}
	arc[0][1]=1;
	arc[0][2]=5; 
	arc[1][2]=3; 
	arc[1][3]=7; 
	arc[1][4]=5; 

	arc[2][4]=1; 
	arc[2][5]=7; 
	arc[3][4]=2; 
	arc[3][6]=3; 
	arc[4][5]=3;

	arc[4][6]=6;
	arc[4][7]=9; 
	arc[5][7]=5; 
	arc[6][7]=2; 
	arc[6][8]=7;

	arc[7][8]=4;

	for(int i = 0; i < N; i++)
	{
		for(int j = i; j < N; j++)
		{
			arc[j][i] =arc[i][j];
		}
	}
	for(int i=0;i<N;i++)
		vexs[i]=i;
}

int main()
{
	init();
	int i,j,k,Min;
	int set[N],dis[N];
	//初始化(这里以V0点开始)
	for(i=0;i<N;i++)
	{
		set[i]=0;
		dis[i]=arc[0][i];
	}
	dis[0]=0;
	set[0]=1;
	//主循环
	for(i=1;i<N;i++)
	{
		Min=65535;
		//把距离v1,v2,v3,....最近的点找出来
		for(j=0;j<N;j++)
		{
			if(!set[j]&&dis[j]<Min)
			{
				k=j;
				Min=dis[j];
			}
		}
		set[k]=1;
		//根据最新找到的最短路径，更新v0点到各节点的最短距离
		for(j=0;j<N;j++)
		{
			if(!set[j]&&(Min+arc[k][j]<dis[j]))
				dis[j]=Min+arc[k][j];
		}
	}
	//输出结果
	for(int i=1;i<N;i++)
		printf("%d ",dis[i]);
}

结果

  1 4 7 5 8 10 12 16              


联系
我们