単一ソース最短問題dijkstraアルゴリズムのまとめ
2364 ワード
Dijkstra(ディジェストラ)アルゴリズムは、1つのノードから他のすべてのノードへの最短パスを計算するために使用されます.このアルゴリズムではパスの重み値に負のエッジは持たないことに注意し,負のエッジがあればbellman fordアルゴリズムを用いる.
dijkstraアルゴリズムを勉強してみると、最小生成ツリーのPrimアルゴリズムと少し似ているような気がします.感覚dijkstraも貪欲な戦略であり,集合Sで表されるのは最小経路が見つかった点であり,dis[]で各点の現在距離源点の最短距離を表す.2点間の距離をもう1つの配列で格納し、直接接続されていない2点についてINFに値を割り当てます.
1、最初は集合Sの中でソースポイントしかありませんでした.
2、最小経路がまだ見つかっていない点のうち、ソース点に最も近い点kを選択し、Sを加え、見つかったことをマークする.
3、さらにk点を中間点として、最小経路が見つからない点のdisを更新し、すなわちdis[k]+map[k][j]4、すべてのノードがSに加わるまで2、3を繰り返す.
特にdijkstraは負のエッジがある場合には使用できないことに注意してください.
個人的には、最小のパスの点を見つけた後、負のエッジがあれば、この負のエッジからこの点まで、あなたが前に見つけた最小のパスよりも小さい可能性があるからだと思います.
例えば無方向図
1 2 1
1 3 2
2 3 -4
このような解釈がorzzzに合っているかどうかは分からない.
例題hdu 2544
コード:
dijkstraアルゴリズムを勉強してみると、最小生成ツリーのPrimアルゴリズムと少し似ているような気がします.感覚dijkstraも貪欲な戦略であり,集合Sで表されるのは最小経路が見つかった点であり,dis[]で各点の現在距離源点の最短距離を表す.2点間の距離をもう1つの配列で格納し、直接接続されていない2点についてINFに値を割り当てます.
1、最初は集合Sの中でソースポイントしかありませんでした.
2、最小経路がまだ見つかっていない点のうち、ソース点に最も近い点kを選択し、Sを加え、見つかったことをマークする.
3、さらにk点を中間点として、最小経路が見つからない点のdisを更新し、すなわちdis[k]+map[k][j]
特にdijkstraは負のエッジがある場合には使用できないことに注意してください.
個人的には、最小のパスの点を見つけた後、負のエッジがあれば、この負のエッジからこの点まで、あなたが前に見つけた最小のパスよりも小さい可能性があるからだと思います.
例えば無方向図
1 2 1
1 3 2
2 3 -4
このような解釈がorzzzに合っているかどうかは分からない.
例題hdu 2544
コード:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define M 1009
#define INF 0x3f3f3f3f
int dis[M]; //dis[i] i
int vis[M]; // i s （ ）
int map[M][M]; //
int n,m;
void dijsktra(int s) //s
{
for(int i = 1;i <= n;i++)
dis[i] = map[s][i]; //
dis[s] = 0;
vis[s] = 1;//
for(int i = 1;i < n;i++)
{
int min = INF;
int k;
for(int j = 1;j <= n;j++)
{
if(!vis[j] && dis[j] < min) //
{
min = dis[j];
k = j;
}
}
if(min==INF) return ; //
vis[k] = 1;
for(int j = 1;j <= n;j++)
{
if(!vis[j] && dis[j] > dis[k]+map[k][j]) // dis k k j dis[j] dis[j]
dis[j] = dis[k]+map[k][j];
}
}
}
int main()
{
while(scanf("%d %d",&n,&m)==2 && (n||m))
{
memset(vis,0,sizeof(vis));
for(int i = 1;i <= n;i++)
for(int j = 1;j <= n;j++)
map[i][j] = INF;
for(int i = 0;i < m;i++)
{
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
map[a][b]=map[b][a]=c; //
}
dijsktra(1);
printf("%d
",dis[n]);
}
return 0;
}