首页 > 代码库 > 对dijkstra的浅见（引例 poj 2457）

对dijkstra的浅见（引例 poj 2457）

2024-07-10 14:04:18   224人阅读

非负权值的单源最短路之 dijkstra

Tanky Woo之dijkstra:  http://www.wutianqi.com/?p=1890


dijkstra-------我认为这个算法的核心思想是：最短路径长度递增。其实就是一个贪心算法。

怎么理解呢？

      最短路的最优子结构：假如有一条最短路径已经存在了，那么其中任意两点的路径都将是最短的，否则假设是不成立了。


算法实现过程：

  1.      已当前点 pos 更新，dis[ i ]的值（即 点 i 到源点的距离）
  2.      找出dis[ i ] 最小的 i 点，作为当前 pos 点，并且加入集合 S ，
  3.      重复 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.

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.

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.

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.



题意：物品交换：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 的前驱点进行改变，所以每进行一遍松弛操作，就要更新前驱结点。



















联系
我们