吴文虎图论中的一个求最短路的方法
只需要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;
}
分享到:
相关推荐
- 对每个顶点\( v \),记录一个标记,表示从\( S \)到\( v \)的最短路径的权值(P标号)或最短路径权值的一个上界(T标号)。 - 在每一步中,更新T标号,并将一个具有T标号的顶点转变为具有P标号的顶点,使得具有P...
算法通过不断更新T标号,将当前最小的T标号点转为P标号,直至终点vt被标记为P标号,此时算法结束,所有P标号的路径即为最短路径。 在实际开发中,使用Delphi 7.0这样的编程环境,可以方便地实现最短路径问题的算法...
在IT领域,优化问题是一个广泛的研究方向,而求解最短路径问题则是一个经典的优化问题。这通常出现在网络分析、物流规划、交通工程以及计算机科学的图论问题中。本主题将聚焦于如何利用LINGO(Linear Interactive ...
经典Dijkstra算法的主要思想 Dijkstra算法的基本思路是:假设每个点都有一对标号 (dj, pj),其中dj是从起源点s到点j的最短路径的长度 (从顶点到其本身的最短路径是零路(没有弧的路),其长度等于零);pj则是从s到j的...
智能算法是指使用机器学习、深度学习等技术,来解决K最短路径问题。 K最短路径问题的应用非常广泛。例如,在交通运输领域中,K最短路径算法可以用于计算从起点到终点的最短路径,提高交通效率。在通信网络领域中,K...
本实验以Dijkstra算法作为解决最短路径问题的核心工具,该算法是图论中的经典算法之一,广泛应用于路径规划、交通网络优化等领域。 Dijkstra算法的基本思想是逐步构造从起点到各个点的最短路径。算法分为以下几个...
1. 初始化:将起点设为已知最短路径点,赋予0距离(标号P),其他所有点设为未知最短路径点(标号T)。 2. 检查当前标号为T的所有点,找到与起点连接且距离最短的边,更新其终点的最短路径和距离。 3. 将找到的最短...
两种算法实现最短路径的寻找,包括点对点,以及单对多
语法:result=Dijkstra... 最短路径长度 注意: 输入的图的权必须非负 顶点标号从0开始 用如下方法打印路径: i=t; while (i!=s) { printf("%d,i+1); i=path[i]; } printf("%d\n",s+1);
2. 临时性标号:是源顶点经过已获得永久性标号的顶点到达某个顶点的路径的最小权值,它是最短路径的上界。 算法步骤如下: 1. 初始化:源顶点v1的永久性标号为0,其他顶点的临时性标号设为从v1出发的边权值,未通过...
关于最短路径问题,目前公认的最佳求解方法之一是由F.W. Dijkstra提出的标号法,即Dijkstra算法。 #### 二、Dijkstra算法 Dijkstra算法是一种求解最短路径的基本且广泛应用的算法。在求从网络中的某一节点(源点)...
Dijkstra算法是解决这类问题的经典算法之一,主要用于找出从一个起点到所有其他点的最短路径。该算法的核心特点是采用标号法,分为暂时性标号T和永久性标号P,确保找到的路径是全局最优的。 Dijkstra算法的基本步骤...
总结,Matlab提供了强大的工具和环境来解决最短路径问题,无论是理论学习还是实际应用,都是一种非常有效的手段。通过Floyd算法和Dijkstra算法,我们可以处理各种类型的网络图,找到最佳的路径策略。在进行编程实现...
在算法的实施过程中,一个顶点的P标号(Permanent Label)表示该顶点已被确定为当前最短路径树的一部分,而T标号(Temporary Label)则表示该顶点可能还不是最终结果。通过不断更新顶点的T标号,并将其转化为P标号,...
文章中还提到了Dijkstra算法,这是最短路径问题中最著名的算法之一,它使用贪心策略,从起始点出发,逐步扩展到达各点的最短路径。Dijkstra算法的主要缺点是不能同时求出多条最短路径,即它只能得到从起点到终点的一...
最小生成树和最短路径算法是图论中的关键概念,广泛应用于计算机科学,特别是网络优化问题。最小生成树算法寻找一个树形结构,这棵树包含了图中的所有顶点,并且树的所有边的权重之和最小。常用的最小生成树算法有...
文章通过一系列步骤具体解析了如何使用标号法求解某一节点到网络其它所有顶点之间的最短路径,并给出了详细的求解实例,帮助读者深入理解算法的工作机制。 适用人群:对数据挖掘、图形算法感兴趣的开发者以及相关...
例如,从v1到v3的最短路径为3,因此v3的T标号被更新为3。 - **第三步**:重复此过程,直至所有节点都被处理完毕。 #### 五、迪杰斯特拉算法的应用 迪杰斯特拉算法在多个领域有着广泛的应用: - **网络路由**:在...