单源最短路
正权边
朴素dijkstra(稠密)O()
int g[N][N], dis[N], n, m;//g[N][N]为邻接矩阵用于存储每条边,dis[N]存储某个点到1号点的最小距离, n为点数,m为边数 |
例题
|
堆优化dijikstra(稀疏)O(mlogn)
typedef pair<int, int> P; |
例题:
|
负权边
bellman-floyd O(mn)
int n, m; // n表示点数,m表示边数 |
例题
|
spfa O(m)-O(mn)
int h[N], w[N], ne[N], e[N], idx;//用邻接表储存边 |
例题
|
多源最短路
floyd O()
int dis[N][N], n, m, k; |
例题
|