网站改版seo方案,网站开发及流行框架,建设目标网站,百度关键词首页排名最短路径#xff08;DP的应用#xff09; 单源最短路径#xff0c;不允许出现负环 核心思想#xff1a;更新估算距离#xff0c;松弛 δ(u,v)≤δ(u,x)δ(x,v)\delta(u, v) \leq \delta(u, x) \delta(x, v) δ(u,v)≤δ(u,x)δ(x,v)
时间复杂度与采用的数据结构有关DP的应用 单源最短路径不允许出现负环 核心思想更新估算距离松弛 δ(u,v)≤δ(u,x)δ(x,v)\delta(u, v) \leq \delta(u, x) \delta(x, v) δ(u,v)≤δ(u,x)δ(x,v)
时间复杂度与采用的数据结构有关标准的dijkstra应该是用堆实现的。 Array O(v2v^2v2) Binary heap O((VE)lgV(VE)lgV(VE)lgV) Fibonacci heap O(EVlgVEVlgVEVlgV)
如果对于所有的边权值均为1那么Dijkstra算法可以用BFS实现 使用FIFO队列代替Priority队列其时间复杂度为O(VEVEVE)
数组实现
#include iostream
using namespace std;
void dijkstra();
int e[10][10];
int vis[10];
int dis[10];
int n, m;
int min1 99999999;
int u 0;
int main()
{cin 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] 99999999;}}}// 填充数据for (int i 1; i m; i){int a, b, c;cin a b c;e[a][b] c;}for (int i 1; i n; i){dis[i] e[1][i];}vis[1] 1;dijkstra();for (int i 1; i n; i){cout dis[i];}system(pause);return 0;
}
void dijkstra()
{for (int i 1; i n - 1; i){min1 99999999;// 寻找权值最小的点ufor (int j 1; j n; j){if (vis[j] 0 dis[j] min1){min1 dis[j];u j;}}vis[u] 1;for (int v 1; v n; v){// 对于每个u可达的v来说if (e[u][v] 99999999){// 如果当前的dis[v]不满足三角形不等式那么进行松弛操作if (dis[v] dis[u] e[u][v]){dis[v] dis[u] e[u][v];}}}}
}堆实现
#include iostream
#include cstdio
#include cstring
#include queue
#include vector
using namespace std;
const int Ni 10000;
const int INF 1 27;
struct node
{int point, value;// 构造node(int a, int b){point a;value b;}// 重载操作符bool operator(const node a) const{// 对小于运算符进行重载如果两个值相等那么继续判断point如果不等则返回falseif (value a.value){return point a.point;}else{return value a.value;}}
};
vectornode e[Ni];
int dis[Ni], n;
priority_queuenode q;
void dijkstra();
int main()
{int a, b, c, m;scanf(%d%d, n, m);while (m--){scanf(%d%d%d, a, b, c);e[a].push_back(node(b, c));e[b].push_back(node(a, c));}// for (int i 0; i n; i)// {// dis[i] INF;// }memset(dis, 0x3f, sizeof(dis));dis[1] 0;// 优先队列队头元素最大但是如果类型为struct需要重载运算符q.push(node(1, dis[1]));dijkstra();for (int i 1; i n; i){printf(%d , dis[i]);}system(pause);return 0;
}
void dijkstra()
{while (!q.empty()){node x q.top();q.pop();for (int i 0; i e[x.point].size(); i){node y e[x.point][i];if (dis[y.point] dis[x.point] y.value){dis[y.point] dis[x.point] y.value;q.push(node(y.point, dis[y.point]));}}}
}
