题意：n个点m条边，然后输入m条无向边和每条边的权值。问1 ~ n的最小路径。
Floyd
思路：来源：传送门
1.邻接矩阵g储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！,。
2.遍历从
到
，作为中继点依次加入图中。每个点加入进行试探是否有路径长度被更改。
3.而上述试探具体方法为遍历图中每一个点(双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点
距离就更改。
4.重复上述直到最后插点试探完成。
5.k必须在最外层，否则不满足dp的无后效性：
采用动态规划思想，表示是i经过编号为
的节点到j的最短路径
初值为原图的邻接矩阵
则可由
转移得到，表示
到
的最短路径不经过k这个点
但也可以从和
转移得到，表示
到
的最短路径经过k这个点
状态转移方程即
然后就会发现f最外层的一维空间可以省略，因为只与
有关，所以算法实现时，
要放在最外层。
6.举例说明：
加入第一个节点1,大家可以发现，由于1的加入，使得本来不连通的2，3点对和2，4点对变得联通，并且加入1后距离为当前最小。(可以很直观加入5之后2，4更短但是还没加入)。为了更好的描述其实此时的直接联通点多了两条：(2,3)和(2,4)。我们在dp中不管这个结果是通过前面那些步骤来的，但是在这个状态，这两点的最短距离就算它！
同时你可以发现加入1其中也使得3,1,4这样联通，但是 3,1,4联通的话距离为9远远大于本来的(3,4)为2，所以不进行更新。
当然这些红色的连线都是代表当前的最短路径。 这也和我们的需求贴合，我们最终要的是所有节点的最短路径。每个节点最终都应该有6条指向不同节点的边！ 表示邻接矩阵的最终结果。
code：
#include<bits/stdc++.h>
using namespace std;
const int inf =1e6;
const int num=105;
int graph[num][num];
int n,m;
void floyd() {
int s=1;
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i) if(graph[i][k]!=inf)
for(int j=1;j<=n;++j) if(graph[i][j]>graph[i][k]+graph[k][j])
graph[i][j]=graph[i][k]+graph[k][j];//min会比if慢，poj 3259会卡掉min
printf("%d\n",graph[s][n]);
}
int main() {
while(~scanf("%d%d",&n,&m)) {
if(!n&&!m) return 0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
graph[i][j]=inf;
while(m--) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
graph[a][b]=graph[b][a]=c;
}
floyd();
}
return 0;
}
/*
6 8
1 2 2
1 3 3
1 4 6
3 4 2
4 5 1
4 6 3
5 2 4
6 2 6
打印路径：
#include<bits/stdc++.h>
using namespace std;
const int inf =1e6;
const int num=105;
int graph[num][num],g[num][num];
int n,m;
void floyd() {
int s=1;
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i) if(graph[i][k]!=inf)
for(int j=1;j<=n;++j) if(graph[i][j]>graph[i][k]+graph[k][j])
graph[i][j]=graph[i][k]+graph[k][j];//min会比if慢，poj 3259会卡掉min
printf("%d\n",graph[s][n]);
}
void print(int a,int b) {
if(graph[a][b]==g[a][b]) printf("%d->",a);
for(int k=1;k<=n;++k) if(graph[a][b]==graph[a][k]+graph[k][b]) {
print(a,k);
print(k,b);
break;
}
}
int main() {
while(~scanf("%d%d",&n,&m)) {
if(!n&&!m) return 0;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
graph[i][j]=inf,g[i][j]=0;
while(m--) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=c;
graph[a][b]=graph[b][a]=c;
}
floyd();
print(1,n);
printf("%d\n",n);
}
return 0;
}
*/ SPFA
其实是用队列优化Bellman-Foed算法。SPFA很像BFS。
参考博客：传送门
#include<bits/stdc++.h>
using namespace std;
const int inf=INT_MAX/10,maxn=10005;
int to[maxn<<1],Next[maxn<<1],w[maxn<<1],head[maxn],tot;
int n,m,cnt;
int dis[maxn];//记录所有结点到起点的最短距离
bool inq[maxn];//inq[i]=true；表示结点i在队列中
int Neg[maxn];//判断负圈
int pre[maxn];//记录前驱结点
void print(int s,int t) {
if(s==t) {printf("%d\n",s); return;}
print(s,pre[t]);
printf("%d ",t);
}//打印从起点s到t的最短路径
void add(int u,int v,int val) {
to[++tot]=v;
Next[tot]=head[u];
w[tot]=val;
head[u]=tot;
}
bool spfa(int s) {
fill(Neg,Neg+maxn,0);
Neg[s]=1;
for(int i=1;i<=n;++i) {dis[i]=inf; inq[i]=false;}
dis[s]=0;
queue<int>q;
q.push(s);
inq[s]=true;
while(!q.empty()) {
int u=q.front(); q.pop();
inq[u]=false;
for(int i=head[u];i;i=Next[i]) {
int v=to[i],val=w[i];
if(dis[u]+val<dis[v]) {
dis[v]=dis[u]+val;
pre[v]=u;
if(!inq[v]) {
inq[v]=true;
q.push(v);
++Neg[v];
if(Neg[v]>n) return true;
}
}
}
}
printf("%d\n",dis[n]);
//print(s,t);
return false;
}
int main() {
while(~scanf("%d%d",&n,&m)){
fill(head,head+maxn,0); tot=0;
if(!n) return 0;
while(m--) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
spfa(1);
}
return 0;
} Dijkstra
来源：传送门
在单源正权值最短路径，我们会用Dijkstra算法来求最短路径，并且算法的思想很简单——贪心算法:每次确定最短路径的一个点然后维护(更新)这个点周围点的距离加入预选队列，等待下一次的抛出确定。但是虽然思想很简单，实现起来是非常复杂的，我们需要前向星储存长度，需要优先队列(或者每次都比较)维护一个预选点的集合。还要用一个vis数组标记是否已经确定、还要---------
总之，Dijkstra算法的思想上是很容易接受的，但是实现上其实是非常麻烦的。但是单源最短路径没有更好的办法。复杂度也为O(n2)
#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct edge{
int to,w;
edge(int a,int b) {to=a;w=b;}
};
vector<edge>e[105];
struct node{
int id,dis;
node(int a,int b){id=a;dis=b;}
bool operator<(const node&a ) const
{return dis>a.dis;}
};
int n,m;
int pre[105]; //记录前驱结点
void print(int s,int t) {
if(s==t) {printf("%d ",s); return;}//打印起点
print(s,pre[t]);//先打印前一个点
printf("%d ",t);//后打印当前点，最后打印的是终点t
}//打印从s到t的最短路径
void dijkstra() {
int s=1; //起点是1
int dis[105];//记录所有结点到起点的距离
bool done[105];//done[i]=true表示到结点i的最短路径已经找到
for(int i=1;i<=n;++i) {
dis[i]=inf; done[i]=false;
}
dis[s]=0; //起点到自己的距离是0
priority_queue<node>q;//优先队列，存结点的信息
q.push(node(s,dis[s]));//起点进栈
while(!q.empty()) {
node u=q.top();
q.pop();
if(done[u.id]) continue;//丢弃已经找到最短路径的结点，即集合A中的结点
done[u.id]=true;
for(int i=0;i<e[u.id].size();++i) {
edge y=e[u.id][i]; //u.id的第i个邻居是y.to
if(done[y.to]) continue;//丢弃已经找到最短路径的邻居结点
if(dis[y.to]>y.w+u.dis) {
dis[y.to]=y.w+u.dis;
q.push(node(y.to,dis[y.to]));//扩展新的邻居，放到优先队列中
pre[y.to]=u.id;//如有需要，打印路径
}
}//检查结点u的所有邻居
}
printf("%d\n",dis[n]);
//print_path(s,n);
}
int main() {
while(~scanf("%d%d",&n,&m)) {
if(!n&&!m) return 0;
for(int i=1;i<=n;++i) e[i].clear();
while(m--) {
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
e[a].push_back(edge(b,c));
e[b].push_back(edge(a,c));
}
dijkstra();
}
}
京公网安备 11010502036488号