📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 7220| 回复: 26
跳转到指定楼层
上一主题 下一主题
收起左侧

Stanford Design and Analysis of Algorithm I 第二期 Week#5 自由讨论

全局:
Topics:This week covers two topics. The first topic (Part XI) is the climax of all our work on graph search --- Dijkstra's shortest-path algorithm, surely one of the greatest hits of algorithms. It works in any directed graph with non-negative edge lengths, and it computes the shortest paths from a source vertex to all other vertices. Particularly nice is the blazingly fast implementation that uses a heap data structure. Speaking of data structures, they constitute the second topic of the week (Part XII). This is a huge (and hugely useful) topic, and the sixth and final week will also be devoted to them. This week covers heaps and also some hash table basics. My primary goals here are to teach you the operations that these data structures support (along with their running times), and to develop your intuition about which data structures are useful for which sorts of problems.

THE VIDEOS:
There are four videos on Dijkstra's shortest-path algorithm (Part XI). Three are required (the algorithm, examples, and the running time analysis); the proof of correctness is recommended but optional. Part XII begins with a short overview video in which I explain my approach to teaching data structures in this course. The next two videos discuss heaps and some of their applications (required), and some details about how they are typically implemented (optional, recommended for hardcore programmer/computer science types). The next three required videos explain the basics of hash tables, some canonical applications of them, and a high-level discussion of how they are implemented and of "good" hash functions.

THE HOMEWORK:
Problem 5 should solidify your understanding of Dijkstra's shortest-path algorithm, heaps, and hash functions. In the programming project you'll implement Dijkstra's algorithm. You can just implement the basic version, but those of you who want a bigger challenge are encouraged to devise a heap-based implementation.

单选投票, 共有 41 人参与投票
90.24% (37)
9.76% (4)
您所在的用户组没有投票权限

上一篇:讨论点评现在市面的公开课
下一篇:有想法组织Stanford CS106A课程
🔗
xx8833 2012-7-15 00:30:49 | 只看该作者
全局:
本帖最后由 xx8833 于 2012-7-16 16:47 编辑

用C++ STL写了一下Dijkstra,大家参考参考吧
  1. #include <stdio.h>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;

  5. #define UNEXPANDED 99999999
  6. #define MAX_NODE_ID 200

  7. struct ID_DIS
  8. {
  9.         int id,distance;
  10.         bool operator < (const ID_DIS & other) const
  11.         {
  12.                 return distance > other.distance;
  13.         }
  14.         ID_DIS(int p_id,int p_dis):
  15.         id(p_id),distance(p_dis){};
  16. };

  17. vector<ID_DIS> adj[MAX_NODE_ID + 1];
  18. int result[MAX_NODE_ID + 1];
  19. priority_queue<ID_DIS> distance_heap;

  20. int main () {
  21.         FILE *fin  = fopen ("dijkstraData.txt", "r");
  22.         FILE *fout = fopen ("dijkstraData_out2.txt", "w");

  23.         int in_node,in_distance,lead_node;
  24.         char in_char;
  25.         while(fscanf(fin,"%d",&in_node) > 0)
  26.         {
  27.                 fscanf(fin,"%c",&in_char);
  28.                 if(in_char != ',')
  29.                         lead_node = in_node;
  30.                 else
  31.                 {
  32.                         fscanf(fin,"%d",&in_distance);
  33.                         adj[lead_node].push_back(ID_DIS(in_node,in_distance));
  34.                 }
  35.         }

  36.         fill(result,result + MAX_NODE_ID,UNEXPANDED);
  37.         distance_heap.push(ID_DIS(1,0));
  38.         while(!distance_heap.empty())
  39.         {
  40.                 ID_DIS expanding = distance_heap.top();
  41.                 distance_heap.pop();
  42.                 if(result[expanding.id] != UNEXPANDED) continue;
  43.                 result[expanding.id] = expanding.distance;
  44.                 for(int i = 0 ; i < adj[expanding.id].size() ; i ++)
  45.                 {
  46.                         distance_heap.push(ID_DIS(adj[expanding.id][i].id,
  47.                                 expanding.distance + adj[expanding.id][i].distance));
  48.                 }
  49.         }

  50.         fprintf(fout,"%d,%d,%d,%d,%d,%d,%d,%d,%d,%d",
  51.                 result[7],result[37],result[59],result[82],result[99],
  52.                 result[115],result[133],result[165],result[188],result[197]);
  53.        return 0;
  54. }
复制代码
回复

使用道具 举报

🔗
endless 2012-7-15 10:40:33 | 只看该作者
全局:
用C写的,因为数据量很小,所以直接邻接矩阵+遍历了。。。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define MAX 200

void read_graph(int graph[][MAX+1]);
void compute(int graph[][MAX+1]);

int main(void)
{
    int graph[MAX+1][MAX+1];
    int i, j;
    for (i = 0; i <= MAX; i++)
        for (j = 0; j <= MAX; j++)
            graph[j] = -1;
    read_graph(graph);
    compute(graph);
    return 0;
}

void read_graph(int graph[][MAX+1])
{
    FILE * fin = fopen("dijkstraData.txt", "r");
    int i, j, row, node, length;
    char temp;
    bool flag;
    for (i = 1; i <= MAX; i++)
    {
        fscanf(fin, "%d", &row);
        if (row != i)
        {
            printf("row number error\n");
            exit(EXIT_FAILURE);
        }
        flag = true;
        while (flag)
        {
            fscanf(fin, "%d", &node);
            if (getc(fin) != ',')
            {
                printf("input format error\n");
                exit(EXIT_FAILURE);
            }
            fscanf(fin, "%d", &length);
            temp = getc(fin);
            while ((temp == ' ') || (temp == '\t'))
                temp = getc(fin);
            graph[i][node] = length;
            graph[node][i] = length;
        }
    }
    fclose(fin);
}

void compute(int graph[][MAX+1])
{
    int distance[MAX+1] = {0};
    int node, i, j, shortest, total;
    bool computed[MAX+1] = {false};
    computed[1] = true;
    total = MAX;
    while (--total > 0)
    {
        shortest = INT_MAX;
        node = -1;
        for (i = 1; i <= MAX; i++)
            if (computed[i] == true)
                for (j = 1; j <= MAX; j++)
                    if ((graph[i][j] != -1) &&
                            (computed[j] == false) &&
                            (distance[i] + graph[i][j] < shortest))
                    {
                        shortest = distance[i] + graph[i][j];
                        node = j;
                    }
        distance[node] = shortest;
        computed[node] = true;
    }
    printf("%d\n", distance[7]);
    printf("%d\n", distance[37]);
    printf("%d\n", distance[59]);
    printf("%d\n", distance[82]);
    printf("%d\n", distance[99]);
    printf("%d\n", distance[115]);
    printf("%d\n", distance[133]);
    printf("%d\n", distance[165]);
    printf("%d\n", distance[188]);
    printf("%d\n", distance[197]);
}

[/i][/i][/i][/i][/i][/i][/i][/i]
回复

使用道具 举报

🔗
EDream 2012-7-16 20:35:07 | 只看该作者
全局:
有个问题,大家是怎么判断找不到shortest path这种情况的呢,条件该如何构造?
回复

使用道具 举报

🔗
endless 2012-7-16 23:13:47 | 只看该作者
全局:
EDream 发表于 2012-7-16 20:35
有个问题,大家是怎么判断找不到shortest path这种情况的呢,条件该如何构造?

你的意思是节点不可达?将不可达距离标记成-1,如果在X集合中,所有节点到其它非X集合节点的距离都是-1,那说明图就断开不连通了。。。我用的邻接矩阵这次。
回复

使用道具 举报

🔗
EDream 2012-7-17 17:09:40 | 只看该作者
全局:
本帖最后由 EDream 于 2012-7-17 22:40 编辑

看了大家的code深受启发,千呼万唤始出来...

#include <iostream>
#include <fstream>
#include <string>
#include <stdio.h>
#include <vector>
#include <assert.h>
using namespace std;


#define N 200
#define NO_PATH 1000000


//To record adjancency vertex and its length
struct tuple {
        int adjvex;
        int len;
};


//To record data from file
struct node {
        int origvex;
        vector<tuple> adj;
};

struct node G[N+1];
bool isVisited[N+1];
int shortestDistance[N+1];


void createGraphFromFile()
{
        ifstream in;
        struct tuple t_pair;
        string str = "";
        in.open("dijkstraData.txt");
        int i = 1, j = 0;
        
        while (!in.eof()) {
                getline(in, str, '\n');        
                //store origvertex
                int vex_idx = str.find('\t');
                string vex_str = str.substr(0, vex_idx);
                G.origvex = atoi(vex_str.c_str());

                str = str.substr(vex_idx+1);
               
                while (str.length() != 0) {
                        //store adjvertex               
                        int comma_idx = str.find(',');
                        string adjvex = str.substr(0, comma_idx);
                        t_pair.adjvex = atoi(adjvex.c_str());
                        //store length
                        int table_idx = str.find('\t');
                        string len = str.substr(comma_idx+1, comma_idx-table_idx-1);
                        t_pair.len = atoi(len.c_str());
                        //store t_pair
                        G[i].adj.push_back(t_pair);

                        str = str.substr(table_idx+1);
                }
                i++;
        }
}


void Dijkstra()
{
        while (true) {
                int visited = -1;
                int min_dist = NO_PATH;
                shortestDistance[1] = 0;
                //Find the next vertex to be processed
                for (int i = 0; i < N+1; i++) {
                        if (!isVisited[i][i] && shortestDistance[i][i] < min_dist) {
[/i][/i][/i][i][i]
                                visited = i;
                                min_dist = shortestDistance[i];

                        }
                }
                if (visited == -1) break;
                isVisited[visited] = true;
                //compute path of each related vertices
                for (int i = 0; i < G[visited].adj.size(); i++) {
                        shortestDistance[G[visited].adj[i].adjvex] = min(shortestDistance[G[visited].adj[i].adjvex],
[/i][i]
                                G[visited].adj[i].len + shortestDistance[visited]);

                }
        }        
}


void printResult()
{
        cout << shortestDistance[7] << ',';
        cout << shortestDistance[37] << ',';
        cout << shortestDistance[59] << ',';
        cout << shortestDistance[82] << ',';
        cout << shortestDistance[99] << ',';
        cout << shortestDistance[115] << ',';
        cout << shortestDistance[133] << ',';
        cout << shortestDistance[165] << ',';
        cout << shortestDistance[188] << ',';
        cout << shortestDistance[197] << endl;
}


int main()
{
        createGraphFromFile();
        fill(shortestDistance, shortestDistance+N+1, NO_PATH);
        fill(isVisited, isVisited+N+1, false);
        Dijkstra();
        printResult();
        
        return 0;
}


[/i][/i]

[/i][/i][/i][/i][/i][/i]
回复

使用道具 举报

🔗
stephenK 2012-7-18 01:09:32 | 只看该作者
全局:
本帖最后由 stephenK 于 2012-7-18 01:11 编辑

贴个naive的解。没写minheap的版本,下次有空补上吧

  1. #include <iostream>
  2. #include <fstream>
  3. #include <vector>
  4. #include <string>
  5. #include <sstream>
  6. #include <algorithm>
  7. using namespace std;
  8. #define SIZE 200
  9. #define MAX_LEN 1000000

  10. struct Node
  11. {
  12. int number;
  13. vector<int> toNodes;
  14. vector<int> toLens;
  15. int shortestLen;
  16. };

  17. Node Graph[SIZE+1];

  18. void Dijkstra(int source)
  19. {
  20. Graph[source].shortestLen =0;
  21. vector<int> X;
  22. X.push_back(source);
  23. while(X.size()< SIZE)
  24. {
  25.   int min = MAX_LEN;
  26.   int candidate=0;
  27.   for(int i=0;i<X.size();i++)
  28.   {
  29.    for(int j=0;j < Graph[X[i]].toNodes.size();j++)
  30.    {
  31.     if(find(X.begin(), X.end(), Graph[X[i]].toNodes[j]) == X.end())
  32.     {
  33.      if(Graph[X[i]].shortestLen + Graph[X[i]].toLens[j] < min)
  34.      {
  35.        min = Graph[X[i]].shortestLen + Graph[X[i]].toLens[j];
  36.        candidate = Graph[X[i]].toNodes[j] ;
  37.      }
  38.     }
  39.    }
  40.   }
  41.   X.push_back(candidate);
  42.   Graph[candidate].shortestLen = min;
  43. }
  44. }

  45. int main(int argc, char *argv[])
  46. {
  47. int Node=0, temp1=0, temp2=0;
  48. ifstream inf(argv[1]);
  49. while(inf)
  50. {
  51.   string line;
  52.   getline(inf,line);
  53.   stringstream st(line);
  54.   st>>Node;
  55.   Graph[Node].number = Node;
  56.   while(st>>temp1)
  57.   {
  58.    Graph[Node].toNodes.push_back(temp1);
  59.    st.ignore();
  60.    st>>temp2;
  61.    Graph[Node].toLens.push_back(temp2);
  62.    Graph[Node].shortestLen = MAX_LEN;
  63.   }
  64. }
  65. Dijkstra(1);
  66. int test[10]={7,37,59,82,99,115,133,165,188,197};
  67. for (int i=0;i<10;i++)
  68.   cout<<"Len for node "<<test[i]<<" :"<<Graph[test[i]].shortestLen<<endl;
  69. }
复制代码


回复

使用道具 举报

🔗
stephenK 2012-7-18 01:13:12 | 只看该作者
全局:
话说现在还有学分这回事么。。怎么一次都没加上呢
回复

使用道具 举报

🔗
shidaohang 2012-7-19 20:16:25 | 只看该作者
全局:
stephenK 发表于 2012-7-18 01:13
话说现在还有学分这回事么。。怎么一次都没加上呢

同问 我也等着加分了
回复

使用道具 举报

🔗
shidaohang 2012-7-21 01:55:07 | 只看该作者
全局:
终于搞定了week 5的编程题。
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<string.h>
  4. #include<ctype.h>
  5. #define MAX 200

  6. const char INFILE[]="dijkstraData.txt";
  7. struct EDGE        {
  8.   long vertex;
  9.   long weight;
  10.   struct EDGE *next;
  11. };
  12. void fetch_g(struct EDGE **g)        {
  13.   FILE *fp = fopen(INFILE,"r");
  14.   long i,v,w;
  15.   char *token,line[800];
  16.   struct EDGE *node;
  17.   while (fgets(line,800,fp))        {
  18.         token = strtok(line,"\t");       
  19.         i = atoi(token);
  20.         g[i] = malloc(sizeof(struct EDGE));
  21.         g[i]->next = NULL;
  22.         while (token = strtok(NULL,"\t\r\n"))        {
  23.                 sscanf(token,"%ld,%ld",&v,&w);
  24.                 node = malloc(sizeof(struct EDGE));
  25.                 node->vertex = v;
  26.                 node->weight = w;
  27.                 node->next = g[i]->next;
  28.                 g[i]->next = node;
  29.         }
  30.   }
  31. }
  32. void print_g(struct EDGE *g)        {
  33.   struct EDGE *node;
  34.   for (node=g; node->next; node=node->next)
  35.         printf("%ld,%ld\t",node->next->vertex,node->next->weight);
  36.   printf("\n");
  37. }
  38. void HEAP_DECREASE_KEY(long *q,long i,long *d)        {
  39.   long tmp;
  40.   while ((i>1) && (d[q[i/2]]>d[q[i]]))        {
  41.         tmp = q[i];        q[i] = q[i/2]; q[i/2] = tmp;
  42.         i = i/2;
  43.   }
  44. }
  45. void INIT_SINGLE_SOURCE(struct EDGE **g,long s,long *d,long *p)        {
  46.   long i;
  47.   for (i=1; i<=MAX; i++)        {       
  48.         d[i] = 1000000;                //        d[i] = INFINITY
  49.         p[i] = -1;                        //        p[i] = NIL
  50.   }
  51.   d[s]=0;
  52. }
  53. void MIN_HEAPIFY(long *q,long i,long *d)        {
  54.   long left = 2*i, right = 2*i+1, smaller, tmp;
  55.   if ((left<=q[0])&&(q[left]<q[i]))
  56.         smaller = left;
  57.   else
  58.         smaller = i;
  59.   if ((right<=q[0])&&(q[right]<q[smaller]))
  60.         smaller = right;
  61.   if (smaller != i)        {
  62.         tmp = q[smaller]; q[smaller] = q[i]; q[i] = tmp;
  63.         MIN_HEAPIFY(q,smaller,d);
  64.   }
  65. }
  66. long EXTRACT_MIN(long *q, long *d)        {
  67.   long min = q[1];
  68.   q[1] = q[q[0]--];
  69.   MIN_HEAPIFY(q,1,d);
  70.   return min;
  71. }
  72. void REFRESH(long u,struct EDGE **g,long *d,long *p)        {
  73.   struct EDGE *node;
  74.   long v,w;
  75.   for (node=g[u]; node->next; node=node->next)        {
  76.         v = node->next->vertex;
  77.         w = node->next->weight;
  78.         if (d[u]+w<d[v])        {
  79.           d[v]=d[u]+w;
  80.           if (p[v]==(-1))       
  81.                 p[v]=u;
  82.           else
  83.                 REFRESH(v,g,d,p);
  84.         }
  85.   }
  86. }
  87. void Dijkstra(struct EDGE **g, long s)        {
  88.   long *d,*p,*q,i,u;
  89.   struct EDGE *node;
  90.   d = calloc(MAX+1,sizeof(long));
  91.   p = calloc(MAX+1,sizeof(long));
  92.   q = calloc(MAX+1,sizeof(long));
  93.   q[0] = MAX;
  94.   for (i=1; i<=MAX; i++)
  95.         q[i] = i;
  96.   INIT_SINGLE_SOURCE(g,s,d,p);
  97.   while (q[0])        {
  98.         u=EXTRACT_MIN(q,d);
  99.         REFRESH(u,g,d,p);
  100.   }
  101.   printf("%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld,%ld\n",d[7],d[37],d[59],d[82],d[99],d[115],d[133],d[165],d[188],d[197]);
  102. }
  103. void main()
  104. {
  105.   struct EDGE **g;
  106.   g = (struct EDGE **)calloc(MAX+1,sizeof(struct EDGE *));
  107.   fetch_g(g);
  108.   Dijkstra(g,1);
  109. }
复制代码
有几点想说:
1.这次题目光看视频的话太容易晕了,于是我这次严格按照算法导论上面的伪代码
2.我用heap来存放V[G]\S的所有距离,heap构成一个min-priority queue.
3.每次循环取出heap中最小,然后最后的元素补上,heapify
4.容易忽略的是,如果是一个S指向S的edge使得distance发生改变,
那么必须把head vertex刷新一遍,否则是不对的
5.所以,需要一个p[1..MAX]来判断是否在S中

我相信以上这些视频中应该都提到,但都晕晕呼呼地过去了
只有自己做一遍才能真正理解。


回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表