Dijkstraアルゴリズム(c++版)
3084 ワード
最短経路(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( v 2 v^2 v2) Binary heap O( ( V + E ) l g V (V+E)lgV (V+E)lgV) Fibonacci heap O( E + V l g V E+VlgV E+VlgV)
すべてのエッジ重み値が1である場合、Dijkstraアルゴリズムは、Priorityキューの代わりにFIFOキューを使用することをBFSで実現することができ、その時間的複雑さはO(V+E V+E V+E)である.
配列実装:
スタック実装
時間的複雑さは採用したデータ構造に関係し,標準的なdijkstraはスタックで実現されるべきである.Array O( v 2 v^2 v2) Binary heap O( ( V + E ) l g V (V+E)lgV (V+E)lgV) Fibonacci heap O( E + V l g V E+VlgV E+VlgV)
すべてのエッジ重み値が1である場合、Dijkstraアルゴリズムは、Priorityキューの代わりにFIFOキューを使用することをBFSで実現することができ、その時間的複雑さはO(V+E V+E V+E)である.
配列実装:
#include
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;
// u
for (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
#include
#include
#include
#include
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;
}
// a.value;
}
}
};
vector e[Ni];
int dis[Ni], n;
priority_queue 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 dis[x.point] + y.value)
{
dis[y.point] = dis[x.point] + y.value;
q.push(node(y.point, dis[y.point]));
}
}
}
}