Dijkstra算法:
思想:找到距离原点最近的一个顶点,然后以该点为中心进行扩展,最终得到源点到其余各点的最短路径。
缺点:无法解决带负边的图论问题。
输入样例:
6 9 1 (6个点 9条边 起点为1)
1 2 1
1 3 12
2 3 9
2 4 3
3 5 5
4 3 4
4 5 13
4 6 15
5 6 4
输出样例:
0 1 8 4 13 17 (源点到各点的最短距离)
#include <cstdio>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <math.h>
#include <vector>
using namespace std;
const int inf=999999;//0x7fffff
const long long mod=1e9+7;
const double PI=acos(-1);
#include <string.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <math.h>
#include <vector>
using namespace std;
const int inf=999999;//0x7fffff
const long long mod=1e9+7;
const double PI=acos(-1);
int n,m;
int ans=9999999;
bool vis[105];
int dis[105];
int ans=9999999;
bool vis[105];
int dis[105];
struct node{
int u;
int w;
node(int uu,int ww){
u=uu;
w=ww;
}
};
vector<node> v[105];
void Dijkstra(int s){ //Dijkstra算法为单源最短路径算法 s 为起点
memset(dis,inf,sizeof(dis)); //dis数组表示起点 s 到每个点的最小路径
dis[s]=0;
int min,minp;
for(int i=1;i<=n;i++){ //遍历dis数组的每一个最短路径
min=inf;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<min){ //寻找并记录此时dis表的最短路径的值和距离
min=dis[j];
minp=j;
}
}
vis[minp]=1;
for(int u=0;u<v[minp].size();u++){ //寻找此时最短路径的点可到的点 并更新该点的最短路径
node no=v[minp][u];
if(!vis[no.u]&&dis[no.u]>dis[minp]+no.w){
dis[no.u]=dis[minp]+no.w;
}
}
}
}
int main()
{
int x,y,value,s;
cin>>n>>m>>s;
for(int i=1;i<=n;i++){
dis[i]=inf;
}
for(int i=0;i<m;i++){
cin>>x>>y>>value;
v[x].push_back(node(y,value));
}
Dijkstra(s); //s 为起点
for(int i=1;i<=n;i++){ //输出s 到各个点的最短路径
cout<<dis[i]<<" ";
}
return 0;
}
int u;
int w;
node(int uu,int ww){
u=uu;
w=ww;
}
};
vector<node> v[105];
void Dijkstra(int s){ //Dijkstra算法为单源最短路径算法 s 为起点
memset(dis,inf,sizeof(dis)); //dis数组表示起点 s 到每个点的最小路径
dis[s]=0;
int min,minp;
for(int i=1;i<=n;i++){ //遍历dis数组的每一个最短路径
min=inf;
for(int j=1;j<=n;j++){
if(!vis[j]&&dis[j]<min){ //寻找并记录此时dis表的最短路径的值和距离
min=dis[j];
minp=j;
}
}
vis[minp]=1;
for(int u=0;u<v[minp].size();u++){ //寻找此时最短路径的点可到的点 并更新该点的最短路径
node no=v[minp][u];
if(!vis[no.u]&&dis[no.u]>dis[minp]+no.w){
dis[no.u]=dis[minp]+no.w;
}
}
}
}
int main()
{
int x,y,value,s;
cin>>n>>m>>s;
for(int i=1;i<=n;i++){
dis[i]=inf;
}
for(int i=0;i<m;i++){
cin>>x>>y>>value;
v[x].push_back(node(y,value));
}
Dijkstra(s); //s 为起点
for(int i=1;i<=n;i++){ //输出s 到各个点的最短路径
cout<<dis[i]<<" ";
}
return 0;
}
Bellman_Floyd算法:
思路:将起使元素入队,队首元素出队,遍历队首元素连接的节点,每次判断能不能通过队首元素使起使元素到此时遍历的节点,使最短路径变小并更新,到队列为空为止。
有点类似于宽度优先搜索,只是宽度优先搜索出队后不再入队,该算法需要不断更新最短路径,可能需要重新入队。
优点:可以解决带负边的问题。
输入样例:
5 7 1 (5个点 7条边 起点元素1)
1 2 2
1 5 10
2 3 3
2 5 7
3 4 4
4 5 5
5 3 6
输出样例:
0 2 5 9 9(起点到各个点的最短路径)
#include <cstdio> #include <string.h> #include <iostream> #include <algorithm> #include <sstream> #include <math.h> #include <vector> #include <queue> using namespace std; const int inf=999999;//0x7fffff const long long mod=1e9+7; const double PI=acos(-1); int n,m; int ans=9999999; bool vis[105]; int dis[105],u[105]; struct node{ int v; int w; node(int vv,int ww){ v=vv; w=ww; } }; vector<node> v[105]; queue<int> q; void Bellman_Floyd(int s){ memset(dis,inf,sizeof(dis)); //初始化设置所有节点都不可达 dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()){ int no = q.front(); // no队首元素序号 nd队首元素连接节点 q.pop(); for(int i=0;i<v[no].size();i++){ //每次遍历队首节点的连接的节点 判断通过队首节点能否使到达连接节点的最短路径变小并更新 node nd=v[no][i]; if(dis[nd.v]>dis[no]+nd.w){ dis[nd.v]=dis[no]+nd.w; if(!vis[nd.v]){ //此时队首相连节点不在队列中 需要添加队列中并置为访问 vis[nd.v]=1; q.push(nd.v); } } }
vis[no]=0; } } int main() { int x,y,value,s; cin>>n>>m>>s; for(int i=1;i<=m;i++){ cin>>x>>y>>value; v[x].push_back(node(y,value)); } Bellman_Floyd(s); for(int i=1;i<=n;i++){ cout<<dis[i]<<" "; } return 0; }