dijkstra算法是解决单源最短路径问题的经典算法,具有O(N^2)的时间复杂度(N为节点个数),这种算法采用的是贪心策略,它与最小生成树的Prim算法极其相似,这两种算法仅仅是cost[]代表的含义不同。dijkstra算法中的cost[i]表示的是节点i与起点间已知的最短路径长度,而Prim中cost[i]表示的是节点i与S中某个点相连边的最小值。
该算法也是将所有点分成两个集合:属于S,或者不属于S,一旦某个节点被加入到S中,它相应的cost就不会再改变(想想为什么)。初始化只有起点属于S,当所有节点都属于S后,算法结束。
下面是算法描述:
1.初始化起点属于S,并利用起点更新cost[]
2.选取S外节点中cost最小的那个点t,加入到S中,并利用t更新cost[]
3.执行第二步,直到所有点都属于S(每次加入一个点,第二步总共被执行N-1次)
有关Prim请参阅:
http://www.cppblog.com/hoolee/archive/2012/08/06/186482.html下面是poj2387的代码:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 1010
#define MAX 1000000
int mp[LEN][LEN];
int main()
{
int i, j;
int T, N;
//printf("%d\n", sizeof(mp));
while(scanf("%d%d", &T, &N) != EOF)
{
memset(mp, 0, sizeof(mp));
int a, b, c;
for(i = 0; i < T; i++)//read map
{
scanf("%d%d%d", &a, &b, &c);//be carefull when read map,
if(mp[a][b] != 0)// there may exit one more trails between the same two points
{
if(c < mp[a][b])
mp[a][b] = mp[b][a] = c;
}
else
mp[a][b] = mp[b][a] = c;
}
int s[LEN] = {0};//init
int cost[LEN];
s[1] = 1;
for(i = 1; i <= N; i++)
if(mp[1][i] != 0)
cost[i] = mp[1][i];
else
cost[i] = MAX;
for(i = 1; i <= N - 1; i++)//dijkstra
{
int t = 1;
int min = MAX;
for(j = 1; j <= N; j++)
if(s[j] == 0 && cost[j] < min)
{
t = j;
min = cost[j];
}
s[t] = 1;
for(j = 1; j <= N; j++)
{
if(s[j] == 0 && mp[t][j] != 0 && cost[t] + mp[t][j] < cost[j])
cost[j] = cost[t] + mp[t][j];
}
}
printf("%d\n", cost[N]);
}
//system("pause");
}
posted on 2012-08-08 16:27
小鼠标 阅读(1857)
评论(0) 编辑 收藏 引用 所属分类:
图论