博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Dijkstra模版
阅读量:5339 次
发布时间:2019-06-15

本文共 1108 字,大约阅读时间需要 3 分钟。

const int MAXN = 205;const int INF = 999999;int n;int maps[MAXN][MAXN];bool visited[MAXN];int pre[MAXN];int dist[MAXN];void init(){	memset(visited, false, sizeof(visited));	for (int i = 1; i <= n; i++)	{		for (int j = 1; j <= n; j++)		{			if(i == j)			{				maps[i][j] = 0;			}			else			{				maps[i][j] = INF;			}		}		pre[i] = i;		dist[i] = INF;	}}void Dijkstra(int s, int e) //起点,终点{	int i, j;	int minValue, minNode;	dist[s] = 0;	visited[s] = true;	for (i = 1; i <= n; i++)	{		dist[i] = maps[s][i];		if(dist[i] == INF)		{			pre[i] = 0;		}		else		{			pre[i] = s;		}	}	for (i = 1; i <= n; i++)	{		minValue = INF;		minNode = 0;		for (j = 1; j <= n; j++)		{			if(!visited[j] && minValue > dist[j])			{				minNode = j;				minValue = dist[j];			}		}		if(minNode == 0)		{			break;		}		visited[minNode] = true;		for (j = 1; j <= n; j++)		{			if(!visited[j] && maps[minNode][j] != INF && dist[j] > dist[minNode] + maps[minNode][j])			{				dist[j] = dist[minNode] + maps[minNode][j];				pre[j] = minNode;			}		}		if(minNode == e)		{			break;		}	}}

转载于:https://www.cnblogs.com/lgh1992314/archive/2013/05/11/5835062.html

你可能感兴趣的文章
kettle导数到user_用于left join_20160928
查看>>
较快的maven的settings.xml文件
查看>>
随手练——HDU 5015 矩阵快速幂
查看>>
SDK目录结构
查看>>
malloc() & free()
查看>>
Django之Models
查看>>
Linux 的 date 日期的使用
查看>>
Java变量类型,实例变量 与局部变量 静态变量
查看>>
mysql操作命令梳理(4)-中文乱码问题
查看>>
Python环境搭建(安装、验证与卸载)
查看>>
一个.NET通用JSON解析/构建类的实现(c#)
查看>>
Windows Phone开发(5):室内装修 转:http://blog.csdn.net/tcjiaan/article/details/7269014
查看>>
详谈js面向对象 javascript oop,持续更新
查看>>
关于这次软件以及pda终端的培训
查看>>
jQuery上传插件Uploadify 3.2在.NET下的详细例子
查看>>
如何辨别一个程序员的水平高低?是靠发量吗?
查看>>
新手村之循环!循环!循环!
查看>>
正则表达式的用法
查看>>
线程安全问题
查看>>
下拉刷新
查看>>