• 采用matlab语言编写高效程序，实现快速又高效的最短路和次短路算法
• 次短路

2018-05-31 00:53:44
问题：对于一个带权图，求两个顶点之间的次短路。概念：次短路表示除最短路以外长度最小的路径类别一：可以重复经过一个点。解法：这个类别解法和求最短路相似，在进行 dijkstra 的过程中记录两个数组：dist0 和 ...
问题：对于一个带权图，求两个顶点之间的次短路。
概念：次短路表示除最短路以外长度最小的路径
类别一：可以重复经过一个点。
解法：这个类别解法和求最短路相似，在进行 dijkstra 的过程中记录两个数组：dist0 和 dist1，分别表示最短路和次短路的答案。每次更新时需要依次判断是否可以更新次短路和最短路的值。由于需要计算次短路，所以调整后的 dijkstra 算法需要至少循环 2n-1 次才可以获得最终答案。
证明：如果我们要求解起点s到终点t的次短路，其中t周围有相邻节点u（u不止一个），那么有两种可能的情况：（1）起点s到顶点u的最短路+d(u,t)，即u不在t的最短路径上。（2）起点到顶点u的次短路+d(u,t)，即u在t的最短路径上。
类别二：不能重复经过一个点。
解法暴力，枚举两个顶点之间最短路上的每条边，每次在去掉这条边的剩下的图中计算最短路，取其中最小的一个答案就是最终次短路的答案。
展开全文
• 题解：这是一道次短路的题目，刚刚学完最短路，发现还有次短路，第k短路问题，刚好就找到了模板题目，次短路就是找到一条仅比最短路短，比其他路都长的路径。在网上看了挺久的，感觉不是很容易理解，就自己根据网上...
原题连接：http://poj.org/problem?id=3255 Roadblocks Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 24585 Accepted: 8540 Description Bessie has moved to a small farm and sometimes enjoys returning to visit one of her best friends. She does not want to get to her old home too quickly, because she likes the scenery along the way. She has decided to take the second-shortest rather than the shortest path. She knows there must be some second-shortest path. The countryside consists of R (1 ≤ R ≤ 100,000) bidirectional roads, each linking two of the N (1 ≤ N ≤ 5000) intersections, conveniently numbered 1…N. Bessie starts at intersection 1, and her friend (the destination) is at intersection N. The second-shortest path may share roads with any of the shortest paths, and it may backtrack i.e., use the same road or intersection more than once. The second-shortest path is the shortest path whose length is longer than the shortest path(s) (i.e., if two or more shortest paths exist, the second-shortest path is the one whose length is longer than those but no longer than any other path). Input Line 1: Two space-separated integers: N and R Lines 2…R+1: Each line contains three space-separated integers: A, B, and D that describe a road that connects intersections A and B and has length D (1 ≤ D ≤ 5000) Output Line 1: The length of the second shortest path between node 1 and node N Sample Input 4 4 1 2 100 2 4 200 2 3 250 3 4 100 Sample Output 450 Hint Two routes: 1 -> 2 -> 4 (length 100+200=300) and 1 -> 2 -> 3 -> 4 (length 100+250+100=450) Source USACO 2006 November Gold
题解：这是一道次短路的题目，刚刚学完最短路，发现还有次短路，第k短路问题，刚好就找到了模板题目，次短路就是找到一条仅比最短路短，比其他路都长的路径。在网上看了挺久的，感觉不是很容易理解，就自己根据网上的解释自己总结一下
1.通过求得的1到2-n个点的最短路，和n到1-(n-1)个点的最短路，如果2-(n-2)分别相互匹配，min(dist1[2….n-1]+distn[2…n-1])，肯定得到最小值。
2.上面而min(dist1[2….n-1]+distn[2…n-1])可以得到最短路 在edge[m]的m个条边中如果存在u->v的边，权是w。 那么dist1[u]+distn[v]+w肯定小于dist1n，但又不至于最长。 但是dist1[u]+distn[v]+w有多条，那么min(dist1[u]+distn[v]+w)就是这当中最短路，也就是次短路了。
定义： 边节点：
struct edge{//边节点
int value;//权
int to;//指向节点
int next;
}edges[MAX*2];

头结点：
int head[MAX/2];//存储每个节点的头

最短路的两个数组：
int dist1[MAX/2],dist2[MAX/2];//最短路辅助数组

访问控制数组：
int v[MAX/2];

边的数量：
int cnt;//存储多少条边

因为这里用到邻接表，之前没有用过，这里介绍一个好的帖子 https://blog.csdn.net/qq_42241901/article/details/81489645
邻接表加边函数：
//insert edge
edges[cnt].to=to;
edges[cnt].value=value;
edges[cnt].to=u;
edges[cnt].value=value;
return ;
}

这里的head看了半天才懂（数据结构学的不够好。。。），利用原题数据顺便画图介绍一下 4 4 1 2 100 2 4 200 2 3 250 3 4 100  每次加边h[u]都是存储着u的上一个边的下标，比如2，在加第二条边的时候，h[2]=1，在加第三条边的时候，h[2]=3。所以连接是从后面连接回来，如果输出的话就是从最后加的边输出回去。
回归正题，有了边之后，就可以求最短路了，那么最短路有四个算法，dijkstra算法，时间效率比较低，Floyd的时间效率更低了，Bellman_Ford在判断负边的时候才会有用，所以我们选择时间效率比较高的spfa算法。
这里简单说一下spfa算法： 先建一个队列辅助，就是如果某个点的值变小，就把这个点加入队列，去寻找有没有引起其他点变小，我们也叫这个队列叫维护队列。有点类似BFS，把这个节点相邻的节点加入队列中，但是不同的是BFS出队之后就不再进入队列，而spfa算法的出队节点还可能入队。 这里推荐一个别人比较好的spfa算法博客：http://www.pianshen.com/article/7830107886/
核心代码1：
void spfa(int u,int *dist){
queue<int> q;
memset(v,0,sizeof(v));
dist[u]=0;
v[u]=1;
q.push(u);
int to,value;
while(!q.empty()){
u=q.front();
q.pop();
v[u]=0;
to=edges[i].to;
value=edges[i].value;
if(dist[to]>dist[u]+value)
{
dist[to]=dist[u]+value;
if(v[to]==0)
{
v[to]=1;
q.push(to);
}
}
}
}
return ;
}

1.把起始节点加入队列 2.出队，找出变小的相邻节点，如果该节点不在队列，加入队列 3.重复循环2，直到队列为空
核心代码2：
for(int i=1;i<=n;i++){
to=edges[j].to;
value=edges[j].value;
temp=dist1[i]+dist2[to]+value;//加入一条边进行比较
if(temp>dist1[n]&&temp<ans)
ans=temp;
}
}

根据最前面的两个推导： 在1到2-n的最小边和n到1-（n-1）的最小边中加入边，然后在加入边的集合中选出最小的边，那么就是次短路了。
AC代码：
#include<iostream>
#include<string.h>
#include<queue>
#define MAX 100005
#define INF 0x3f3f3f3f
using namespace std;
struct edge{//边节点
int value;//权
int to;//指向节点
int next;
}edges[MAX*2];
int dist1[MAX/2],dist2[MAX/2];//最短路辅助数组
int v[MAX/2];
int cnt;//存储多少条边
int n,r;
//初始化
void init(){
cnt=0;
memset(dist1,INF,sizeof(dist1));
memset(dist2,INF,sizeof(dist2));
return ;
}
//insert edge
edges[cnt].to=to;
edges[cnt].value=value;
edges[cnt].to=u;
edges[cnt].value=value;
return ;
}

void spfa(int u,int *dist){
queue<int> q;
memset(v,0,sizeof(v));
dist[u]=0;
v[u]=1;
q.push(u);
int to,value;
while(!q.empty()){
u=q.front();
q.pop();
v[u]=0;
to=edges[i].to;
value=edges[i].value;
if(dist[to]>dist[u]+value)
{
dist[to]=dist[u]+value;
if(v[to]==0)
{
v[to]=1;
q.push(to);
}
}
}
}
return ;
}
int main(){
while(cin>>n>>r){
init();
int u,v,w;
for(int i=0;i<r;i++){
cin>>u>>v>>w;
}
spfa(1,dist1);
spfa(n,dist2);
int ans=INF;
int temp=INF;
int to,value;
for(int i=1;i<=n;i++){
to=edges[j].to;
value=edges[j].value;
temp=dist1[i]+dist2[to]+value;//加入一条边进行比较
if(temp>dist1[n]&&temp<ans)
ans=temp;
}
}
cout<<ans<<endl;
}
return 0;
}

学习博客：https://blog.csdn.net/a17865569022/article/details/78775608
展开全文
• 在图论里，最短路，次短路，k短路的问题很常见。 这里总结一下。 存图技巧 数据小，稠密图的一般用邻接矩阵 稀疏图，数据大一般用邻接表（vector,链式前向星都可) 邻接矩阵 const int maxn = 1e5+5; int Graph[maxn]...
在图论里，最短路，次短路，k短路的问题很常见。 这里总结一下。
存图技巧
数据小，稠密图的一般用邻接矩阵 稀疏图，数据大一般用邻接表（vector,链式前向星都可)
邻接矩阵
const int maxn = 1e5+5;
int Graph[maxn][maxn];	// 正权图可以初始化成-1来判断是否连通，负权图可以再考虑开个数组或者用一个很大的值。

链式前向星
const int maxn = 1e5+5;
struct Edge{
int u,v,nxt;
}edge[maxn];
inline void addedge(int u,int v,int w){	// u->v 权值是w
edge[++tot] = {u,v,w};
}

最短路
一般最短路算法有 BFS(暴力，一般只适用于点数小的情况),dijiastra(解决正权图),spfa(解决负权图，但容易死,被卡),floyed(解决点与点之间的最短距离问题,dp)
这里直接给出单源最短路的算法(因为都挺好理解的) (重点在于松弛操作!)
dijiastra
// 堆优化版本
const int maxn = 1e5+5;
struct Edge{
int u,v,nxt,w;
}edge[maxn];
inline void init(){
}
inline void addedge(int u,int v,int w){
}
int dis[maxn];  bool vis[maxn];
inline void dijiastra(int s){
struct Node{
int u,dis;
bool operator <(const Node &h)const{
return dis > h.dis;
}
};
memset(dis,0x3f,sizeof(dis));   //  视具体情况而定初始化的值
dis[s] = 0;
priority_queue<Node> pq;    pq.push(Node{s,0});
while(!pq.empty()){
Node u = pq.top();  pq.pop();
if(vis[u.u])    continue;
vis[u.u] = true;
for(int i = head[u.u]; ~i; i = edge[i].nxt){
Edge &e = edge[i];
if(dis[e.v] > u.dis + e.w){
dis[e.v] = u.dis + e.w;
pq.push(Node{e.v,dis[e.v]});
}
}
}
}

spfa
struct Edge{
int v,d;
Edge(int vv,int dd):v(vv),d(dd){}
};
struct Node{
int u,cost;
Node(int uu,int cc):u(uu),cost(cc){}
bool operator < (const Node & h)const{
return cost > h.cost;
}
};
const int MAX = 1e5+5;
vector < Edge > edges;
vector < int > Graph[MAX];
bool vis[MAX];
int dp[MAX];
edges.push_back(Edge{v,dis});
Graph[u].push_back(edges.size()-1);
}
void SPFA(int s,int n){
memset(dp,0x3f,sizeof(dp));
dp[s-1] = 0;
priority_queue<Node>q ;
q.push(Node{s-1,0});  vis[s-1] = 1;
while(!q.empty()){
Node x = q.top(); q.pop();
int u = x.u; vis[u] = 0; // cancel the tag;
for(int i = 0; i < Graph[u].size(); ++i ){
Edge & e = edges[Graph[u][i]];
if( dp[e.v] > dp[u]+ e.d ){
dp[e.v] = dp[u] + e.d;
if(!vis[e.v]) q.push(Node{e.v,dp[e.v]});
vis[e.v] = 1;
}
}
}
}

次短路(利用最短路来求)
目前见到的方法一般有两种，遍历or删边
1.删边。 首先使用最短路算法求出

s

−

t

s - t

的最短路,并且记录下最短路的路径(在松弛的时候记录前驱)，然后对于这条路径，我们依次去删去一条边，然后跑最短路，去更新ans
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
const double inf = 1e9+5;
struct Edge{
int u,v,nxt;    double w;
}edge[maxn];
pair<int,int> path[maxn];
inline void addedge(int u,int v,double w){
}
inline void init(){
tot = 0;
}

double dis[maxn];   bool vis[maxn];
bool isok[maxn];
inline void dijiastra(int s){
struct Node{
int u;  double dis;
bool operator <(const Node &h)const{
return dis > h.dis;
}
};
for(int i = 0; i < maxn; ++i)  dis[i] = inf,vis[i] = false;
priority_queue<Node> pq;    pq.push(Node{s,0});
while(!pq.empty()){
Node u = pq.top();  pq.pop();
if(vis[u.u])
continue;
vis[u.u] = true;
for(int i = head[u.u]; ~i; i = edge[i].nxt){
if(isok[i]) continue;
Edge &e = edge[i];
if(dis[e.v] > u.dis + e.w){ //  松弛过程中记录
dis[e.v] = u.dis + e.w;
path[e.v] = make_pair(u.u,i);
pq.push(Node{e.v,dis[e.v]});
}
}
}
}
struct Point{
int x,y;
}p[maxn];
inline double get_dis(const Point &p,const Point&q){
return sqrt( (p.x-q.x)*(p.x-q.x) + (p.y-q.y)*(p.y-q.y));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
init();
int n,m;    cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> p[i].x >> p[i].y;
for(int i = 0,u,v; i < m; ++i){
cin >> u >> v;  double d = get_dis(p[u],p[v]);
}
dijiastra(1);
pair<int,int> tt = path[n];
vector<int> ee; ee.push_back(tt.second);
while(tt.first!=1){
tt = path[tt.first];
ee.push_back(tt.second);
}

double ans = inf;
for(int i = 0; i < ee.size(); ++i){
isok[ee[i]] = true;
dijiastra(1);
isok[ee[i]] = false;
ans = min(ans,dis[n]);
}
if(ans==inf){
cout << -1 << endl;
}
else cout <<fixed<<setprecision(2)<< ans << endl;
return 0;
}


2.遍历。 跑两次最短路，分别是以起点，以终点。 然后遍历所有边，去更新长度

∑

e

(

u

,

v

)

∈

G

(

v

,

e

)

m

i

n

(

d

i

s

[

1

]

[

u

]

+

w

(

u

,

v

)

+

d

i

s

[

v

]

[

n

]

)

\sum_{e(u,v)\in G(v,e)}min(dis[1][u]+w(u,v)+dis[v][n])

k短路 ( A*或者左偏树)（当然也可以用于解决次短路问题)
左偏树，A*待更新
左偏树学习：大佬博客
展开全文
• 思路：问最短路和次短路的条数和，并且次短路只比最短路多1，我们在dijkstra时进行统计和更新，用dis[i][0]表示到i点的最短距离用dis[i][1]表示到i点的次短距离，用cnt[i][0]表示到i的最短路径的条数，用cnt[i][1]...

思路：问最短路和次短路的条数和，并且次短路只比最短路多1，我们在dijkstra时进行统计和更新，用dis[i][0]表示到i点的最短距离用dis[i][1]表示到i点的次短距离，用cnt[i][0]表示到i的最短路径的条数，用cnt[i][1]表示到i的次短路径条数，当我们到 i 点最短路需要更新时,那么原来到 i 的最短路就会变成次短路，先更新一下次短路的距离，此时到 i 次短路的条数也是就变成了之前到 i 的最短路条数，然后我们再更新最短路的距离，最短路的次数也更新，当我们发现和最短路距离相同则我们发现新的路径，只更新到该点的最短路条数，当我们发现此时可以更新次短路距离时，更新次短路距离和路径条数，当发现和次短路距离相同时则只更新次短路条数，
代码：
#pragma GCC optimize(2)
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
const int mod=100003;
const int N=2e5+5;
const int inf=0x7f7f7f7f;

int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}

ll lcm(ll a,ll b)
{
return a*(b/gcd(a,b));
}

template <class T>
{
char c;
bool op = 0;
while(c = getchar(), c < '0' || c > '9')
if(c == '-')
op = 1;
x = c - '0';
while(c = getchar(), c >= '0' && c <= '9')
x = x * 10 + c - '0';
if(op)
x = -x;
}
template <class T>
void write(T x)
{
if(x < 0)
x = -x, putchar('-');
if(x >= 10)
write(x / 10);
putchar('0' + x % 10);
}
ll qsm(int a,int b,int p)
{
ll res=1%p;
while(b)
{
if(b&1)
res=res*a%p;
a=1ll*a*a%p;
b>>=1;
}
return res;
}
struct node
{
int to,nex,w;
}edge[N];
struct Ver
{
int ver,type,dist;
bool operator> (const Ver &W)const
{
return dist>W.dist;
}
};

int tot,bcnt;
int n,m,S,T;
int vis[N][2];
{
edge[tot].to=v;
edge[tot].w=w;
}
int dij()
{
memset(vis,0,sizeof vis);
memset(cnt,0,sizeof cnt);
memset(dis,inf,sizeof dis);
cnt[S][0]=1;
dis[S][0]=0;
priority_queue<Ver,vector<Ver>,greater<Ver> > heap;
heap.push({S,0,0});
while(heap.size())
{
Ver now=heap.top();heap.pop();
int distance=now.dist,type=now.type,ver=now.ver;
int num=cnt[ver][type];
if(vis[ver][type])continue;
vis[ver][type]=1;
{
int v=edge[i].to,w=edge[i].w;

if(dis[v][0]>distance+w)
{
dis[v][1]=dis[v][0];
cnt[v][1]=cnt[v][0];
heap.push({v,1,dis[v][1]});
dis[v][0]=distance+w;
cnt[v][0]=num;
heap.push({v,0,dis[v][0]});
}
else if(dis[v][0]==distance+w)
{
cnt[v][0]+=num;
}
else if(dis[v][1]>distance+w)
{
dis[v][1]=distance+w;
cnt[v][1]=num;
heap.push({v,1,dis[v][1]});
}else if(dis[v][1]==distance+w)
{
cnt[v][1]+=num;
}

}
}
int res=cnt[T][0];
if(dis[T][0]+1==dis[T][1])res+=cnt[T][1];

return res;

}

int main()
{
int t;
scanf("%d",&t);
while(t--)
{

scanf("%d%d",&n,&m);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
}
scanf("%d%d",&S,&T);

printf("%d\n",dij());

}

return 0;

}


展开全文
• 第k短路和次短路

千次阅读 多人点赞 2018-09-08 16:25:19
（1）我们知道在BFS中，第一到达终点就是到终点的最短路，那么第k到达终点，当然就是到终点的第k短路了。但是如果直接BFS搜索下去，时间复杂度会非常高，因此我们需要剪枝，怎么剪枝呢？ （2）我们每次只需要...
• 非常好的算法，使用matlab编成，快速球的最短路和次短路
• 最短路和次短路条数

千次阅读 2017-01-28 22:18:48
给你一张无向图或有向图，要你求任意两点的最短路条数或次短路条数 算法描述：  1，最短路：  对于最短路条数，我们很容易想到的是加法原则，我们可以在用dij求最短路的时候，  当dis[j]=dis[to]+
• 方法一： ... 原因：因为次短路一定至少有一条边和最短路的不一样，我们通过枚举任意一条边，强制一条路一定从这里过。并且这条路的两个端点到1，N两个点的距离是保证最短的。因此当我们找到次短路跟最...
• USACO 2006 November Gold本题目的意思就是要求次短路。我用两种方法求解：（一）利用dijkstra算法进行适当修改，到某个顶点v的次短路：(1)其他某个顶点u的最短路加上u-&gt;v的边长;(2)其他某个顶点u的次短路...
• 题意：在给定有向图中查找最短路与次短路，如果（最短路+1==次短路）则输出（最短路条数+次短路条数），否则只输出最短路条数。 思路：在最短路的松弛操作上做些判断和记录即可，具体看代码吧（有注释）。 #...
• 测试题目 NKOJ1107达喀尔拉力赛 方法一 Bellman-Ford. 计算 S 到任意点的最...显然次短路长度就是 min{ dis[x] + w + sid[y] } .这个方法代码非常好写，也很好想，不过跑了两次最短路，常数略大。 方法二 Dijkst...
• 题目链接 题目含义 一个人想去朋友家，最短路不走，想走次短路，而且长度严格...而求次短路时，如果这个点像求最短路一样出队的话，万一这个点的次短路没求好 那完了，你已经出队了 而且，你队列里装的dis不是指...
• matlab经典算法的程序-最短路和次短路.zip
• Dijkstra应用之次短路

千次阅读 2016-04-29 21:31:22
那么现在我们问题不在是最短路了，而是次短路(第二短的路径)。我们现在还能使用DIjkstra算法吗？当然了，你看到这篇博客的名字就知道了。其实一开始我也没想到用Dijkstra来求解次短路问题，在看《挑战程序设计竞赛》...
• Dijkstra求最短路与次短路

千次阅读 2015-04-28 12:52:45
短路： 假设有如下 无向图： 每条边有权，要求从A到G的最短路，设数组d[i]用来记录每个点到A的最短路，D[][]用来记录权值d[0]=0。先来说一下我一开始的误区，在看了一些介绍这个算法的文章后我大概知道了是要...
• 次短路小结

2018-12-04 18:49:30
次短路有两种计算方法。 方法一、更新最短路时同步更新次短路 对于一条端点为u、v的边，点v的次短路，要么是点u的次短路加边权，要么是点u的最短路加边权。 设两个数组，dist1存储最短路，dist2存储次短路，则存在...
• 首先我们要求出次短路，我们求次短路的方法是：以点1为起点进行一遍spfa,再以点n为起点，进行一遍spfa，然后枚举除了1和n之外的所有点，找出从1~x的最短距离+从n~x的最短距离最小的那个值，这个值就是 次短路 。枚举...
• 两种次短路

2019-04-11 10:33:44
次短路：最短路外的另一条最短路 两种次短路： 可经过重复顶点。 不可经过重复顶点。 如图所示 1->2->1->2->3 1->3 对于第一种次短路直接再加一个数组一起更新即可。 对于第二种次短路，需要...
• 次短路与第K短路 次短路是除了最短路之外第二短的路，这条路的长度有可能和最短路一样长。 第K短路就是第K短的路，鉴于这两个算法都是特别模板的题，直接上例子 HRBUST 1050 Hot Pursuit II 求次短路：Dijkstra的...
• 杂谈次短路

千次阅读 2015-02-03 15:31:25
这是今天遇到的第一个求次短路问题（要是来学具体实现的就不需要看我的这篇啦~，这篇偏向于数学证明） 题意：某街区共有R条道路、N个路口。道路可以双向通行。问1号路口到N号路口的次短路长度是多少? 次短路指的...
• POJ3255，问题是求节点1到n的次短路。 在dijkstra求最短路算法的基础上进行变形，用两个数组分别记录源点到各节点最短路径和次短路径； 每次更新时，都将最短路的节点及可能成为次短路的节点push入队； #include<...
• 次短路求法

2019-08-21 23:10:38
思路很简单，用一个数组dist[i][2]表示从1到 i 的最短和次短路，如果通过某一个点能更新最短路，就更新最短路，最短路既然被更新的说明已经不是最短路了，就把它放到次短路的位置，如果最短路不能别更新，说明它不是...
• 次短路算法： 有两种比较简单实现次短路的思想 方法一：用 dijkstra 算法 从起点开始 同时维护 【最短路数组（dis1[ ]）】 和 【次短路 数组 （dis2[ ]）】 方法二：还是用到dijkstra 算法 分别用两个 dis1[ ] ...

...