图算法小结(prime与dijkstra对比)

（0）Dijstra 最短路径和prim最小生成树算法，神似，只是在更新dist时的if条件不同；主要是这种prime 的计算两个集合间的最小值的思想非常重要。

（1）某省自从实行了很多年的畅通工程计划后，终于修建了很多路。不过路多了也不好，每次要从一个城镇到另一个城镇时，都有许多种道路方案可以选择，而某些方案要比另一些方案行走的距离要短很多。这让行人很困扰。
现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。
Input
本题目包含多组数据，请处理到文件结束。
每组数据第一行包含两个正整数N和M(0<N<200,0<M<1000)，分别代表现有城镇的数目和已修建的道路的数目。城镇分别以0～N-1编号。
接下来是M行道路信息。每一行有三个整数A,B,X(0<=A,B<N,A!=B,0<X<10000),表示城镇A和城镇B之间有一条长度为X的双向道路。
再接下一行有两个整数S,T(0<=S,T<N)，分别代表起点和终点。
Output
对于每组数据，请在一行里输出最短需要行走的距离。如果不存在从S到T的路线，就输出-1.

Sample Input
3 3
0 1 1
0 2 3
1 2 1
0 2
3 1
0 1 1
1 2

Sample Output
2
-1

// prime 和 dij算法的核心 —— 如何保证当前的最小边是最终的最小边，
// 上面试最小生成树的算法，下面是最短路径的算法了
#include <iostream>
#include <cstring>
using namespace std;

const int INF = 1000000;
const int MAX_SIZE = 200;
int map[MAX_SIZE][MAX_SIZE];
bool visited[MAX_SIZE];
int disit[MAX_SIZE]; //存储距离

//s开始位置，e结束位置
void dij_method(int s, int e, int N)
{
    // init the params of dij
    memset(visited, false, sizeof(visited));
    for (int i = 0; i < N; i++)
    {
        if (map[s][i] == -1)
            disit[i] = INF;
        else
            disit[i] = map[s][i];
    }
    // 从s 点开始计算
    visited[s] = true;
    for (int i = 1; i < N; i++)
    {
        int min = INF;
        int index = 0;
        // 找当前最小的 （这与prime一样，只是if条件更强了）
        for (int j = 0; j < N; j++)
        {
            if (!visited[j] && j != s && disit[j] != -1 && disit[j] < min)
            {
                min = disit[j];
                index = j;
            }
        }
        visited[index] = true;//顶点并入U集
        if (index == e) //如果已经达到终点
            break;
        // 调整更新目前的最短距离（这与这与prime一样，只是if条件不一样而已）
        for (int j = 0; j < N; j++)
        {
            if (!visited[j] && map[index][j] != -1
                    && (min + map[index][j]) < disit[j])
            {
                disit[j] = min + map[index][j];
            }
        }// end of for
    }// end of for
}

int main()
{
    int N, M;// 点数和记录数
    int ori, des, len;//
    int start, end;
    while (cin >> N >> M)
    {
        memset(map, -1, sizeof(map)); //-1表示不可达
        while (M--)
        {
            cin >> ori >> end >> len;
            //有可能有更小的路径
            if (map[ori][des] == -1 || len < map[ori][des])
            {
                map[ori][des] = len;
                map[des][ori] = len;
            }
        }
        // input and input start and end.
        cin >> start >> end;

        if (start == end)
        {
            cout << 0 << endl;
            continue;
        }
        // 调用无负权边的图(Dijkstra算法)
        dij_method(start, end, N);

        if (visited[end] && disit[end] < INF)
            cout << disit[end] << endl;
        else
            cout << -1 << endl;
    }
    return 0;
}

（2）* About:    有向图的Dijkstra算法实现
输入数据:
5
7
1 2 10
1 4 30
1 5 100
2 3 50
3 5 10
4 3 20
4 5 60
输出数据:
999999 10 999999 30 100
10 999999 50 999999 999999
999999 50 999999 20 10
30 999999 20 999999 60
100 999999 10 60 999999
源点到最后一个顶点的最短路径长度: 60
源点到最后一个顶点的路径为: 1 -> 4 -> 3 -> 5

#include <iostream>
using namespace std;
 
const int maxnum = 100;
const int maxint = 999999;
 
 
void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum])
{
    bool s[maxnum];    // 判断是否已存入该点到S集合中
    for(int i=1; i<=n; ++i)
    {
        dist[i] = c[v][i];
        s[i] = 0;     // 初始都未用过该点
        if(dist[i] == maxint)
            prev[i] = 0;
        else
            prev[i] = v;
    }
    dist[v] = 0;
    s[v] = 1;
 
    // 依次将未放入S集合的结点中，取dist[]最小值的结点，放入结合S中
    // 一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间的最短路径长度
    for(int i=2; i<=n; ++i)
    {
        int tmp = maxint;
        int u = v;
        // 找出当前未使用的点j的dist[j]最小值
        for(int j=1; j<=n; ++j)
            if((!s[j]) && dist[j]<tmp)
            {
                u = j;              // u保存当前邻接点中距离最小的点的号码
                tmp = dist[j];
            }
        s[u] = 1;    // 表示u点已存入S集合中
 
        // 更新dist
        for(int j=1; j<=n; ++j)
            if((!s[j]) && c[u][j]<maxint)
            {
                int newdist = dist[u] + c[u][j];
                if(newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
    }
}
 
void searchPath(int *prev,int v, int u)
{
    int que[maxnum];
    int tot = 1;
    que[tot] = u;
    tot++;
    int tmp = prev[u];
    while(tmp != v)
    {
        que[tot] = tmp;
        tot++;
        tmp = prev[tmp];
    }
    que[tot] = v;
    for(int i=tot; i>=1; --i)
        if(i != 1)
            cout << que[i] << " -> ";
        else
            cout << que[i] << endl;
}
 
int main()
{
    freopen("input.txt", "r", stdin);
    // 各数组都从下标1开始
    int dist[maxnum];     // 表示当前点到源点的最短路径长度
    int prev[maxnum];     // 记录当前点的前一个结点
    int c[maxnum][maxnum];   // 记录图的两点间路径长度
    int n, line;             // 图的结点数和路径数
 
    // 输入结点数
    cin >> n;
    // 输入路径数
    cin >> line;
    int p, q, len;          // 输入p, q两点及其路径长度
 
    // 初始化c[][]为maxint
    for(int i=1; i<=n; ++i)
        for(int j=1; j<=n; ++j)
            c[i][j] = maxint;
 
    for(int i=1; i<=line; ++i)  
    {
        cin >> p >> q >> len;
        if(len < c[p][q])       // 有重边
        {
            c[p][q] = len;      // p指向q
            c[q][p] = len;      // q指向p，这样表示无向图
        }
    }
 
    for(int i=1; i<=n; ++i)
        dist[i] = maxint;
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=n; ++j)
            printf("%8d", c[i][j]);
        printf("\n");
    }
 
    Dijkstra(n, 1, dist, prev, c);
 
    // 最短路径长度
    cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl;
 
    // 路径
    cout << "源点到最后一个顶点的路径为: ";
    searchPath(prev, 1, n);
}

（3）

//poj2367题意： 知道一个数n， 然后n行，编号1到n, 每行输入几个数，
//该行的编号排在这几个数前面，输出一种符合要求的编号名次排序。
#include <iostream>
#include <cstring>
#include <cstdio>

using namespace std;
const int MAXN = 105;

bool adj[MAXN][MAXN];// 林街边
int in_degree[MAXN];// 入度
int result[MAXN];// 结果顺序

void topo_sort(const int n)
{
    int i,j,k;
    memset(in_degree,0,sizeof(in_degree));
    for(i=1; i<=n; i++)   //寻找入度为零的节点
    {
        for(j=1; j<=n; j++)
        {
            if(adj[i][j])
                in_degree[j]++;
        }
    }// 可以在输入的时候就计算入度的数值

    for(i=1; i<=n; i++)// 这一个i表示个数的
    {
        for(j=1; j<=n; j++)
        {
            if(in_degree[j]==0)
            {
                k=j;
                break;
            }
        }
        in_degree[k]=-1;// 标志，已访问过
        result[i]=k;
        for(j=1; j<=n; j++)  //入度减一
        {
            if(adj[k][j])
            {
                in_degree[j]--;
            }
        }// end of for
    }// end of for
}

int main()
{
    int i,tem;
    int n;
    //init and input
    memset(adj,false,sizeof(adj));
    scanf("%d",&n);
    for(i=1; i<=n; i++)
    {
         while(scanf("%dtem",&tem),tem)
         {
             adj[i][tem]=true;
         }
    }
    // topo_sort
    topo_sort(n);
    for(i=1; i<=n; i++)
    {
        if(i==1)
             printf("%d",result[i]);
        else
            printf(" %d",result[i]);
    }
    printf("\n");
    return 0;
}

POJ 3249 拓扑排序+动态规划
分类： ACM 2012-06-11 13:38 812人阅读 评论(0) 收藏 举报
inputdelete存储struct
该题是让求在一个有向无环图中，从一个入度为 0 的节点出发，到一个出度为 0 的节点的最大的权值问题。我们可以使用广搜，但是会超时，上网查了一下解题报告，可以使用拓扑排序+动态规划来解决此问题:
dp[1] = max{ dp[2] + cost[1] , dp[3] + cost[1] };
dp[2] = cost[2] + dp[4];
dp[3] = cost[3] + dp[4];
dp[4] = cost[4];
dp[5] = cost[5] + dp[6];
dp[6] = cost[6];
在拓扑排序的过程中，是入度为0的节点先入队列，所以我们可以做一个逆置思考，是的 dp[i] 存储的是入度为零的节点到当前节点的最大权值和，而最后在出度为 0 的节点的 dp[i] 中搜索最大的权值。代码实现如下：

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;
#define N 100100
#define M 1000100
#define INF 1<<29

struct node
{
    int v;
    int next;
} edge[M];

int dp[N];  // 最大价值 存储 由 拓扑排序后 入度为0的节点到当前节点最大的 profit
int enext[N];   //记录节点 i 当前的边，由当前的边 推出 下一条边
int indegree[N];    //入度
int cost[N];    //价值
int res;
int idx;
std::queue<int > q;

int m,n,a,b,i,j;
void input()
{
    for(i=1;i<=n;i++)
    {
        scanf("%d",&cost[i]);
        dp[i] = -INF;
        indegree[i] = 0;
    }

    idx=0;

    //memset(dp,-INF,sizeof(int)*(n+10) );
    //memset(indegree,0,sizeof(int)*(n+10) );    //节点度数初始化为0
    memset(enext,-1,sizeof(enext) ); //说明当前节点只此一条边

    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&a,&b);
        edge[idx].v = b;
        edge[idx].next = enext[a];
        enext[a] = idx++;
        indegree[b]++;
    }
    while( !q.empty() )
        q.pop();
    for( i=1;i<=n;i++)
        if( !indegree[i] )
            q.push(i),dp[i]=cost[i];
}


int dag()
{
    res = -INF;
    while( !q.empty() )
    {
        int cur = q.front();
        q.pop();
        bool flag = true;  //只有节点的出度为 0 的时候，我们才判断其是否有最大profit
        int nextid;
       // cout<<"cur : "<<cur<<endl;
        for( i=enext[cur] ; i != -1 ; i = edge[i].next) //遍历当前顶点的所有的边
        {
            flag = false;
            nextid =  edge[i].v ;

        //    cout<<"nextid : "<<nextid<<endl;
            if( dp[nextid] < cost[ nextid ] + dp[cur])
                dp[nextid] =  cost[nextid] + dp[cur];
            indegree[nextid]--;
            if( !indegree[nextid] )
            {
                q.push(nextid);
            }
        }
        if( flag && dp[cur] > res )
            res = dp[cur];
    }
    return res;
}

int main()
{
    while(scanf("%d %d",&n,&m) != EOF)
    {
        input();
        printf("%d\n",dag());
    }
    return 0;
}