一丶Floyd
算法思想:在e[i][j]之间加入1个或者多个中间点(中转站)来观察,时候使得e[i][j]的值变小
即e[i][j]=e[i][k]+e[k][j].
核心代码
void Floyd()
{
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(e[i][k]<INF&&e[k][j]<INF&&e[i][k]+e[k][j]<e[i][j])e[i][j]=e[i][k]+e[k][j];}
完整模板
#include<stdio.h>
#define N 10
#define INF 0x3f3f3f3f
int n,m;
int e[N][N];
void init()
{
//n表示顶点个数,m表示边的个数 scanf("%d %d",&n,&m);//初始化 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) e[i][j]=0;else e[i][j]=INF;//读入边 for(int i=1;i<=m;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);e[x][y]=z;}
}
void Floyd()
{
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(e[i][k]<INF&&e[k][j]<INF&&e[i][k]+e[k][j]<e[i][j])e[i][j]=e[i][k]+e[k][j];}
int main()
{
init();Floyd();for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)printf("%10d",e[i][j]);printf("\n");} }
/*测试数据 1 4 4 2 3 3 3 1 7 3 4 1 4 1 5 4 3 12 输出结果0 2 5 49 0 3 46 8 0 15 7 10 0*/
二丶Dijkstar
算法思想:
先求出起始位置到达各个点之间的距离,不能到达即为INF(无穷)
//初始化 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) e[i][j]=0;else e[i][j]=INF;//初始化dis数组,这里是1号顶点到其余各个顶点的初始路程 for(int i=1;i<=n;i++)dis[i] = e[1][i];
然后求从起点出发经过某些中间点,来观察时候使得e[i][j]变小,flag[u]数组的作用是标记已经算出从起点(i)出发经过中间点u到达终点(j)的值.
for(int i=1;i<=n-1;i++){
int min = INF;int u;for(int j=1;j<=n;j++){
//找到离1号顶点最近的点 if(flag[j]==0&&dis[j]<min){
min = dis[j];u=j;}}flag[u] = 1;for(int v=1;v<=n;v++){
if(e[u][v]<INF){
if(dis[v]>dis[u]+e[u][v])dis[v]=dis[u]+e[u][v];}}}
完整模板
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0x3f3f3f3f
#define N 10
using namespace std;
int dis[N],e[N][N];
int flag[N];
int n,m;
void init()
{
//n表示顶点个数,m表示边的个数 scanf("%d%d",&n,&m);//初始化 for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) e[i][j]=0;else e[i][j]=INF;//读入边for(int i=1;i<=m;i++){
int x,y,z;scanf("%d%d%d",&x,&y,&z);//选择相同2点中的最小值 if(z<e[x][y])e[x][y]=e[y][x]=z;}//初始化dis数组,这里是1号顶点到其余各个顶点的初始路程 for(int i=1;i<=n;i++)dis[i] = e[1][i]; //初始化book数组 memset(flag,0,sizeof(flag));flag [1]=1; /*//若干改为某个点(k)开始而不是从1号顶点开始for(int i=1;i<=n;i++)dis[i] = e[k][i]; dis[k] = 0;for(int i=1;i<=n;i++)flag[i] = 0;flag[k]=1;*/ }void Dijkstra()
{
for(int i=1;i<=n-1;i++){
int min = INF;int u;for(int j=1;j<=n;j++){
//找到离1号顶点最近的点 if(flag[j]==0&&dis[j]<min){
min = dis[j];u=j;}}flag[u] = 1;for(int v=1;v<=n;v++){
if(e[u][v]<INF){
if(dis[v]>dis[u]+e[u][v])dis[v]=dis[u]+e[u][v];}}} }
int main()
{
init();Dijkstra();for(int i=1;i<=n;i++)printf("%d ",dis[i]);
}
/*测试数据 6 9 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*/
三丶Bellman-ford
算法思想等同于Dijkstar,就是解决了Dijkstar不能处理负权值的问题.
完整模板
#include <iostream>
#define N 100
#define INF 0x3f3f3f3f
using namespace std ;// 边，
typedef struct Edge
{
int u, v ; // 起点，重点int weight ; // 边的权值
}Edge ;
Edge edge [N] ; // 保存边的值
int dist [N] ; // 结点到源点最小距离
int nodenum, edgenum, source ; // 结点数，边数，源点
// 初始化图
void init ( )
{
// 输入结点数，边数，源点cin >> nodenum >> edgenum >> source ;for ( int i = 1 ; i <=nodenum ; ++i )dist [i] = INF ;dist [source] = 0 ;for ( int i = 1 ; i <=edgenum ; ++i ){
cin >> edge [i]. u >> edge [i]. v >> edge [i]. weight ;//注意这里设置初始情况if (edge [i]. u == source ) dist [edge [i]. v] = edge [i]. weight ;}
}
/* void relax ( int u, int v, int weight ) {if (dist [v ] > dist [u ] + weight )dist [v ] = dist [u ] + weight ; } */
bool Bellman_Ford ( )
{
for ( int i = 1 ; i <=nodenum - 1 ; ++i ){
int check = 0; //用来标记本轮松弛中的数组dis是否更新 for ( int j = 1 ; j <=edgenum ; ++j )if (dist [edge [j]. v] > dist [edge [j]. u] + edge [j]. weight ){
check = 1; //数组dis发生更新 dist [edge [j]. v] = dist [edge [j]. u] + edge [j]. weight ;}//松弛结束后检查数组dis是否更新if(check == 0) break;//如果数组dis没有更新,提前结束算法. }//relax (edge [j ]. u, edge [j ]. v, edge [j ]. weight ) ;bool flag = 1 ;// 判断是否有负环路for (int i = 1 ; i <=edgenum ; ++i )if (dist[edge [i]. v]>dist[edge [i]. u]+edge[i].weight){
flag = 0 ;break ;}return flag ;
}
int main ( )
{
init( );if (Bellman_Ford( ))for (int i=1;i<=nodenum;i ++)cout<<dist[i]<<" ";return 0 ;
}
/* 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 40 1 8 4 13 17 */