`
Coco_young
  • 浏览: 125578 次
  • 性别: Icon_minigender_1
  • 来自: 湖南长沙
社区版块
存档分类
最新评论

学习日志_最短路径之标号法

 
阅读更多

吴文虎图论中的一个求最短路的方法

只需要O(ElogE)的时间复杂度就可以求出单源结点的所有最短路径, 实现的时候使用优先队列来维护可选的弧集,代码如下:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAXN = 110;
struct gnode;
vector<gnode> g[MAXN];
int mark[MAXN],d[MAXN];
struct gnode
{
	int v,val;
};
struct node
{
   int u,v;
   int dist;
   bool operator < (const node &n) const
   {
	   return dist>n.dist;
   }
};
void clear()
{
	for(int i=0;i<MAXN;i++)g[i].clear();
}
int shortest_way(int s,int n)
{
	memset(mark,0,sizeof(mark));
	memset(d,-1,sizeof(d));
	d[s]=0;
	mark[s]=1;
	priority_queue<node> PQ;
	node now;
	int i,cnt=0;
	for(i=0;i<g[s].size();i++)
	{
		now.u = s; now.v = g[s][i].v;
		now.dist = d[s]+g[s][i].val;
		PQ.push(now);
	}
	while(!PQ.empty())
	{
		do
		{
			if(PQ.empty())return cnt;
			now = PQ.top();
			PQ.pop();
			//cnt++;
		}while(mark[now.v]);
		//cout<<now.v<<endl;
		d[now.v] = now.dist;
		mark[now.v] = 1;int v = now.v;
		for(i=0;i<g[v].size();i++)
		{
			if(!mark[g[v][i].v]){
				now.u = v; now.v = g[v][i].v;
				now.dist = d[v]+g[v][i].val;
				PQ.push(now);
			}
		}
	}
	return 0;
}
int main()
{
	int n,m;
	while(scanf("%d%d",&n,&m),n||m)
	{
		clear();
		gnode gnow;
		for(int i=0;i<m;i++)
		{
			int a,b,c;
			scanf("%d%d%d",&a,&b,&c);
			gnow.v = b; gnow.val = c;
			g[a].push_back(gnow);
			gnow.v = a; gnow.val = c;
			g[b].push_back(gnow);
		}
		int cnt = shortest_way(1,n);
		cout<<d[n]<<endl;
	}
	return 0;
}


分享到:
评论

相关推荐

    最短路径算法及应用.pdf

    - 对每个顶点\( v \),记录一个标记,表示从\( S \)到\( v \)的最短路径的权值(P标号)或最短路径权值的一个上界(T标号)。 - 在每一步中,更新T标号,并将一个具有T标号的顶点转变为具有P标号的顶点,使得具有P...

    图论中最短路径问题算法程序的开发1

    算法通过不断更新T标号,将当前最小的T标号点转为P标号,直至终点vt被标记为P标号,此时算法结束,所有P标号的路径即为最短路径。 在实际开发中,使用Delphi 7.0这样的编程环境,可以方便地实现最短路径问题的算法...

    利用lingo软件求最短路径

    在IT领域,优化问题是一个广泛的研究方向,而求解最短路径问题则是一个经典的优化问题。这通常出现在网络分析、物流规划、交通工程以及计算机科学的图论问题中。本主题将聚焦于如何利用LINGO(Linear Interactive ...

    最短路径的选择

    经典Dijkstra算法的主要思想 Dijkstra算法的基本思路是:假设每个点都有一对标号 (dj, pj),其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);pj则是从s到j的...

    top K最短路径问题(K Shortest Path Routing)K最短路径算法与应用分析.pdf

    智能算法是指使用机器学习、深度学习等技术,来解决K最短路径问题。 K最短路径问题的应用非常广泛。例如,在交通运输领域中,K最短路径算法可以用于计算从起点到终点的最短路径,提高交通效率。在通信网络领域中,K...

    运筹学最短路径实验借鉴.pdf

    本实验以Dijkstra算法作为解决最短路径问题的核心工具,该算法是图论中的经典算法之一,广泛应用于路径规划、交通网络优化等领域。 Dijkstra算法的基本思想是逐步构造从起点到各个点的最短路径。算法分为以下几个...

    运筹学最短路径实验.pdf

    1. 初始化:将起点设为已知最短路径点,赋予0距离(标号P),其他所有点设为未知最短路径点(标号T)。 2. 检查当前标号为T的所有点,找到与起点连接且距离最短的边,更新其终点的最短路径和距离。 3. 将找到的最短...

    Floyed 迪杰斯特拉最短路径

    两种算法实现最短路径的寻找,包括点对点,以及单对多

    Dijstra算法单源最短路径

    语法:result=Dijkstra... 最短路径长度 注意: 输入的图的权必须非负 顶点标号从0开始 用如下方法打印路径: i=t; while (i!=s) { printf("%d,i+1); i=path[i]; } printf("%d\n",s+1);

    离散数学最短路径和关键路径PPT学习教案.pptx

    2. 临时性标号:是源顶点经过已获得永久性标号的顶点到达某个顶点的路径的最小权值,它是最短路径的上界。 算法步骤如下: 1. 初始化:源顶点v1的永久性标号为0,其他顶点的临时性标号设为从v1出发的边权值,未通过...

    Dijkstra最短路径算法的优化及其实现

    关于最短路径问题,目前公认的最佳求解方法之一是由F.W. Dijkstra提出的标号法,即Dijkstra算法。 #### 二、Dijkstra算法 Dijkstra算法是一种求解最短路径的基本且广泛应用的算法。在求从网络中的某一节点(源点)...

    配送运输管理最短路径算法PPT学习教案.pptx

    Dijkstra算法是解决这类问题的经典算法之一,主要用于找出从一个起点到所有其他点的最短路径。该算法的核心特点是采用标号法,分为暂时性标号T和永久性标号P,确保找到的路径是全局最优的。 Dijkstra算法的基本步骤...

    Matlab基础:最短路径问题.ppt

    总结,Matlab提供了强大的工具和环境来解决最短路径问题,无论是理论学习还是实际应用,都是一种非常有效的手段。通过Floyd算法和Dijkstra算法,我们可以处理各种类型的网络图,找到最佳的路径策略。在进行编程实现...

    利用 Matlab 编程计算最短路径及中位点选址

    在算法的实施过程中,一个顶点的P标号(Permanent Label)表示该顶点已被确定为当前最短路径树的一部分,而T标号(Temporary Label)则表示该顶点可能还不是最终结果。通过不断更新顶点的T标号,并将其转化为P标号,...

    最短路径动态规划问题及C语言实现.pdf

    文章中还提到了Dijkstra算法,这是最短路径问题中最著名的算法之一,它使用贪心策略,从起始点出发,逐步扩展到达各点的最短路径。Dijkstra算法的主要缺点是不能同时求出多条最短路径,即它只能得到从起点到终点的一...

    最小生成树 最短路径算法.pdf

    最小生成树和最短路径算法是图论中的关键概念,广泛应用于计算机科学,特别是网络优化问题。最小生成树算法寻找一个树形结构,这棵树包含了图中的所有顶点,并且树的所有边的权重之和最小。常用的最小生成树算法有...

    MATLAB算法介绍:图论中Dijkstra最短路径计算原理与方法详解

    文章通过一系列步骤具体解析了如何使用标号法求解某一节点到网络其它所有顶点之间的最短路径,并给出了详细的求解实例,帮助读者深入理解算法的工作机制。 适用人群:对数据挖掘、图形算法感兴趣的开发者以及相关...

    迪杰斯特拉最短路径算法及应用

    例如,从v1到v3的最短路径为3,因此v3的T标号被更新为3。 - **第三步**:重复此过程,直至所有节点都被处理完毕。 #### 五、迪杰斯特拉算法的应用 迪杰斯特拉算法在多个领域有着广泛的应用: - **网络路由**:在...

Global site tag (gtag.js) - Google Analytics