首页 > 代码库 > 对dijkstra的浅见(引例 poj 2457)
对dijkstra的浅见(引例 poj 2457)
非负权值的单源最短路之 dijkstra
Tanky Woo之dijkstra: http://www.wutianqi.com/?p=1890
dijkstra-------我认为这个算法的核心思想是:最短路径长度递增。其实就是一个贪心算法。
怎么理解呢?
最短路的最优子结构:假如有一条最短路径已经存在了,那么其中任意两点的路径都将是最短的,否则假设是不成立了。
算法实现过程:
- 已当前点 pos 更新,dis[ i ]的值(即 点 i 到源点的距离)
- 找出dis[ i ] 最小的 i 点,作为当前 pos 点,并且加入集合 S ,
- 重复 1 ,2步骤,N次,因为每次都会找出一个点,一共只有N个点;
以poj 2457为例:
Part Acquisition
Description
The cows have been sent on a mission through space to acquire a new milking machine for their barn. They are flying through a cluster of stars containing N (1 <= N <= 50,000) planets, each with a trading post.
The cows have determined which of K (1 <= K <= 1,000) types of objects (numbered 1..K) each planet in the cluster desires, and which products they have to trade. No planet has developed currency, so they work under the barter system: all trades consist of each party trading exactly one object (presumably of different types).
The cows start from Earth with a canister of high quality hay (item 1), and they desire a new milking machine (item K). Help them find the best way to make a series of trades at the planets in the cluster to get item K. If this task is impossible, output -1.
The cows have determined which of K (1 <= K <= 1,000) types of objects (numbered 1..K) each planet in the cluster desires, and which products they have to trade. No planet has developed currency, so they work under the barter system: all trades consist of each party trading exactly one object (presumably of different types).
The cows start from Earth with a canister of high quality hay (item 1), and they desire a new milking machine (item K). Help them find the best way to make a series of trades at the planets in the cluster to get item K. If this task is impossible, output -1.
Input
* Line 1: Two space-separated integers, N and K.
* Lines 2..N+1: Line i+1 contains two space-separated integers, a_i and b_i respectively, that are planet i‘s trading trading products. The planet will give item b_i in order to receive item a_i.
* Lines 2..N+1: Line i+1 contains two space-separated integers, a_i and b_i respectively, that are planet i‘s trading trading products. The planet will give item b_i in order to receive item a_i.
Output
* Line 1: One more than the minimum number of trades to get the milking machine which is item K (or -1 if the cows cannot obtain item K).
* Lines 2..T+1: The ordered list of the objects that the cows possess in the sequence of trades.
* Lines 2..T+1: The ordered list of the objects that the cows possess in the sequence of trades.
Sample Input
6 5 1 3 3 2 2 3 3 1 2 5 5 4
Sample Output
4 1 3 2 5
Hint
OUTPUT DETAILS:
The cows possess 4 objects in total: first they trade object 1 for object 3, then object 3 for object 2, then object 2 for object 5.
The cows possess 4 objects in total: first they trade object 1 for object 3, then object 3 for object 2, then object 2 for object 5.
题意:物品交换:n个交换方式,k是目标物品,用物品1 换k,求最少交换的次数。
思路:建图 map[u][v]=1,权值为 1,表示一次交换,即每条路都是一种交换方式,由题是单向图。
代码:
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define INF 0x3f3f3f3f #define maxn 1000+10 using namespace std; int map[maxn][maxn]; int dis[maxn]; int pre[maxn]; int kind; void dijkstra(int s) { int vis[maxn],minn,pos; memset(vis,0,sizeof vis); for(int i=0;i<kind+1;i++) dis[i]=INF; dis[s]=0; for(int i=0;i<kind;i++) { minn=INF; for(int j=1;j<=kind;j++) if(!vis[j]&&minn>dis[j]) { minn=dis[j]; pos=j; } vis[pos]=1; for(int j=1;j<=kind;j++) if(!vis[j]&&dis[j]>dis[pos]+map[pos][j]) { pre[j]=pos; dis[j]=dis[pos]+map[pos][j]; //每更新一遍dis ,刷新一遍 pre } } } void print_path(int aim) //路径输出函数 { int n=dis[aim]; // dis是多少,就交换了多少次,有多少个前驱。 int path[maxn]; //倒着记录路径 int step=0,temp; path[++step]=aim; temp=aim; printf("%d\n",n+1); for(int i=0;i<n;i++) { temp=pre[temp]; path[++step]=temp; } for(int i=step;i>=1;i--) //倒着输出 printf("%d\n",path[i]); } int main() { int n,k; while(scanf("%d%d",&n,&k)!=EOF) { int u,v; kind=-1; for(int i=0;i<maxn;i++) for(int j=0;j<maxn;j++) map[i][j]=INF; for(int i=0;i<n;i++) { scanf("%d%d",&u,&v); map[u][v]=1; if(kind<max(u,v)) kind=max(u,v); } dijkstra(1); if(dis[k]<INF) print_path(k); else printf("-1\n"); } return 0; }
当然了,这一题还涉及了一个对最短路径的输出问题。
如何输出呢?
设置一个pre [ i ]=pos 数组,记录点 i 的前驱点 pos
为何要设置前驱点呢?
因为dijkstra更新dis【】的时候是根据 pos点更新的,所以每更新一次,就要刷新一遍pre[ ]数组;
即:仅仅只有松弛操作,会对点 v 的前驱点进行改变,所以每进行一遍松弛操作,就要更新前驱结点。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。