今天学了floyd和dijkstra算法。
floyd算法基本思想：最刚开始只允许经过1号顶点进行中转，接下来只允许经过1和2号顶点进行中转......允许经过1~n号所有顶点进行中转，求任意两点之间的最短路程。
代码实现如下：
#include<stdio.h>
#define inf 0x3f3f3f3f
int e[51][51];
int main()
{int 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;}}int t1,t2,t3;for(int i=1; i<=m; i++){scanf("%d%d%d",&t1,&t2,&t3);e[t1][t2]=t3;}//核心代码for(int i=1; i<=n; i++)//所被允许的中转点for(int j=1; j<=n; j++)for(int k=1; k<=n; k++)if(e[j][k]>e[j][i]+e[i][k])e[j][k]=e[j][i]+e[i][k];for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){printf("%d ",e[i][j]);}printf("\n");}return 0;
}
dijkstra算法基本思想：每次找到离源点最近的一个顶点，然后通过该顶点的所有出边来松弛源点到其余各顶点的路程（即扩展），被松弛过的的点需要被标记，以防下次被访问到。
代码实现如下：
//dijkstra算法
#include<stdio.h>
#define inf 0x3f3f3f3f
int e[10001][10001],dis[10001],book[10001];
int main()
{int n,m,start;scanf("%d%d%d",&n,&m,&start);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;}}int t1,t2,t3,u;for(int i=1;i<=m;i++){scanf("%d%d%d",&t1,&t2,&t3);e[t1][t2]=t3;}//初始化dis数组for(int i=1;i<=n;i++){dis[i]=e[start][i];}book[start]=1;//核心代码for(int i=1;i<=n-1;i++)//除源点外有n-1个点需要扩展{int min=inf;for(int j=1;j<=n;j++){if(book[j]==0&&dis[j]<min){min=dis[j];u=j;}}book[u]=1;for(int j=1;j<=n;j++)//更新与u相连点的dis[]{if(e[u][j]<inf){if(dis[j]>dis[u]+e[u][j])dis[j]=dis[u]+e[u][j];}}}for(int i=1;i<=n;i++){printf("%d ",dis[i]);}return 0;
}
总结：floyd算法在代码上比较简单，也可以处理带有负权边的图（负权回路除外），但时间复杂度较高。dijkstra算法时间复杂度是N平方，但不可以处理带有负权边的图
随后我用dijkstra算法尝试的做了一道题
究其原因应该是我是用邻接矩阵存的图，爆内存了，明天我会学习邻接表来尝试优化。