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

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

🔗
企鹅大哥 2012-7-22 12:34:32 | 只看该作者
全局:
coursera的网站down掉了?咋个老是登录不进去呢
回复

使用道具 举报

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

按题目要求,将所有节点与source节点的最短路径设为1000000(相当于无穷大)。如果找得到最短路径,距离会被修改。最后,所有与source节点最短路径仍然是1000000的节点,就是不存在最短路径的节点。
回复

使用道具 举报

🔗
asterid 2012-7-22 13:28:18 | 只看该作者
全局:
本帖最后由 asterid 于 2012-7-22 13:31 编辑

也上传次代码,攒攒学分。
Python新手,一大半代码都用来读文件生成edge_list了……

  1. def gen_edge_list(filename):
  2.     myfile=open(filename)
  3.     str=myfile.read()
  4.     direct_input=str.split('\n')
  5.     myfile.close()
  6.     #delete last empty line
  7.     direct_input=direct_input[:-1]
  8.     #element in temp_element is ['vertex,distance','vertex,distance',...]
  9.     temp_element=[]
  10.     for e in direct_input:
  11.         temp_element.append(e.split())
  12.     #element in final_list is [[vertex,distance],[vertex,distance],...]
  13.     final_list=[]
  14.     i=0
  15.     n=len(temp_element)
  16.     while i<n:
  17.         temp_element[i]=temp_element[i][1:]
  18.         final_list.append([])
  19.         for e in temp_element[i]:
  20.             ver,dis=e.split(',')
  21.             final_list[i].append([int(ver),int(dis)])
  22.         i=i+1
  23.     #element in edge_list is [vertex1,vertex2,dis]
  24.     edge_list=[]
  25.     i=0
  26.     n=len(final_list)
  27.     while i<n:
  28.         #print i
  29.         for e in final_list[i]:
  30.             edge_list.append([i+1,e[0],e[1]])        
  31.         i=i+1
  32.     return edge_list

  33. #v0 is the source vertex
  34. #node is the total number of nodes in G, from #1 to #node
  35. def dijkstra_naive(edge_list,v0,node):
  36.     #shortest path distances, final output; the first element, index 0, is just for convenience and not meaningful.
  37.     A=[1000000]*(node+1)
  38.     A[v0]=0
  39.     #list of vertices processed
  40.     X=[]
  41.     X.append(v0)
  42.     while len(X)<node:
  43.         dis=1000000
  44.         v,w=0,0
  45.         for e in edge_list:
  46.             if e[0] in X and e[1] not in X:
  47.                 if A[e[0]]+e[2]<dis:
  48.                     v=e[0]
  49.                     w=e[1]
  50.                     dis=A[e[0]]+e[2]                    
  51.         X.append(w)
  52.         A[w]=dis
  53.     return A

  54. filename='F://dijkstraData.txt'
  55. edge_list=gen_edge_list(filename)
  56. v0=1
  57. node=200
  58. A=dijkstra_naive(edge_list,v0,node)
  59. print A[7],A[37],A[59],A[82],A[99],A[115],A[133],A[165],A[188],A[197]
复制代码

回复

使用道具 举报

🔗
touchzou 2012-7-22 19:01:14 | 只看该作者
全局:
看到一次就得六分,很有成就感,Yeah! 木有没采用Heap,有空再采用Heap,上周的SCC还没有搞定啊...
  1. #include <stdio.h>
  2. #include <stdlib.h>

  3. #undef __test
  4. //#define __test

  5. #ifdef __test
  6. #define MAX 4
  7. #endif

  8. #ifndef MAX
  9. #define MAX 200
  10. #endif

  11. struct node
  12. {
  13.     int label;
  14.     int weight;
  15.     struct node * next;
  16. };
  17. void init(struct node *, int);
  18. void add_edge(int, int, int, struct node*, int);

  19. struct node graph[MAX + 1];


  20. int X[MAX + 1], V_X[MAX + 1];

  21. void dijkstra(int, struct node *, int);


  22. void read_data(char *, struct node *, int);

  23. int A[MAX + 1];



  24. int main(void)
  25. {
  26.     int x;
  27.     for(x = 0; x <= MAX; x++)
  28.     {
  29.         A[x] = 1000000;
  30.         X[x] =  -1;
  31.         V_X[x] = x;
  32.     }
  33.     int length = MAX;
  34. #ifndef __test
  35.     read_data("D:\\dijkstraData.txt", graph, length);
  36. #endif

  37. #ifdef __test
  38.     add_edge(1, 2, 1, graph, length);
  39.     add_edge(1, 3, 4, graph, length);
  40.     add_edge(2, 3, 2, graph, length);
  41.     add_edge(2, 4, 4, graph, length);
  42.     add_edge(3, 4, 3, graph, length);

  43.     add_edge(2, 1, 1, graph, length);
  44.     add_edge(3, 1, 4, graph, length);
  45.     add_edge(3, 2, 2, graph, length);
  46.     add_edge(4, 2, 4, graph, length);
  47.     add_edge(4, 3, 3, graph, length);
  48. #endif
  49.     dijkstra(1, graph, length);
  50. #ifdef __test
  51.     int num = 4;
  52.     int shortest[4] = {1, 2, 3, 4};
  53. #endif
  54. #ifndef __test
  55.     int num = 10;
  56.     int shortest[10] = {7,37,59,82,99,115,133,165,188,197};
  57. #endif
  58.     printf("Destinations:");
  59.     for(x = 0; x < num; x++)
  60.     {
  61.         printf("%d,", shortest[x]);
  62.     }
  63.     printf("\n");
  64.     printf("Shortest paths: ");
  65.     for(x = 0; x < num; x++)
  66.     {
  67.         printf("%d,", A[shortest[x]]);
  68.     }
  69.     printf("\n");
  70.     return 0;
  71. }

  72. void init(struct node * data, int len)
  73. {
  74.     int x;
  75.     for(x = 1; x <= len; x++)
  76.     {
  77.         (data + x)->label = x;
  78.         (data + x)->weight = 0;
  79.         (data + x)->next = NULL;
  80.     }
  81. }

  82. void add_edge(int origin, int to, int weight, struct node * data, int len)
  83. {
  84.     if(origin == to)
  85.     {
  86.         printf("Don't allow self loop.\n");
  87.         return;
  88.     }
  89.     else if(origin > len || to > len)
  90.     {
  91.         printf("Impossible edge!\n");
  92.         return;
  93.     }
  94.     struct node * temp = data + origin;
  95.     while(temp->next != NULL)
  96.     {
  97.         if(temp->label == to)
  98.         {
  99.             printf("Edge is existed!\n");
  100.             printf("%d -> %d\n", origin, to);
  101.             return;
  102.         }
  103.         temp = temp->next;
  104.     }
  105.     temp->next = (struct node *)malloc(sizeof(struct node));
  106.     temp->next->label = to;
  107.     temp->next->next = NULL;
  108.     temp->next->weight = weight;
  109. }


  110. void dijkstra(int origin, struct node * data, int len)
  111. {
  112.     X[origin] = origin;
  113.     V_X[origin] = -1;
  114.     A[origin] = 0;

  115.     int x = 1;
  116.     while(x < len)
  117.     {

  118.         int dijkstra_min = -1, to_v = -1;
  119.         int y;
  120.         for(y = 1; y <= len; y++)
  121.         {
  122.             // For every vertex in V.

  123.             if(X[y] != -1)
  124.             {
  125.                 //printf("%d ->", X[y]);
  126.                 struct node * temp_point = (data + y)->next;
  127.                 while(temp_point != NULL)
  128.                 {
  129.                     //printf("%d ", temp_point->label);
  130.                     // Wrong direction. Don't allow it.
  131.                     if(V_X[temp_point->label] == -1)
  132.                     {
  133.                         temp_point = temp_point->next;
  134.                         continue;
  135.                     }
  136.                     // Assume X contain {w,s}, V - X contain {v, t}, and the edge is w->v, s->t
  137.                     // then the shortest path is min{A[w] + Lwv, A[s] + Lst].
  138.                     if(dijkstra_min == -1)
  139.                     {
  140.                         dijkstra_min = A[y] + temp_point->weight;
  141.                         to_v = temp_point->label;
  142.                     }
  143.                     else
  144.                     {
  145.                         if(dijkstra_min > A[y] + temp_point->weight)
  146.                         {
  147.                             dijkstra_min = A[y] + temp_point->weight;
  148.                             to_v = temp_point->label;
  149.                         }
  150.                     }
  151.                     temp_point = temp_point->next;
  152.                 }
  153.             }
  154.         }
  155.         if(to_v == -1)
  156.         {
  157.             // Cann't go to other vertex.
  158.             break;
  159.         }
  160.         else
  161.         {
  162.             X[to_v] = to_v;
  163.             V_X[to_v] = -1;
  164.             A[to_v] = dijkstra_min;
  165.         }
  166.         x++;
  167.     }

  168. }

  169. void read_data(char * file, struct node * data, int len)
  170. {
  171.     FILE *fp = fopen(file, "rb");
  172.     while(!feof(fp))
  173.     {
  174.         int origin, to, weight;
  175.         fscanf(fp, "%d", &origin);
  176.         int mark = 1;
  177.         while(mark)
  178.         {
  179.             fscanf(fp, "%d,%d ", &to, &weight);
  180.             add_edge(origin, to, weight, data, len);
  181.             int previous, next;
  182.             next = fgetc(fp);
  183.             if(next == EOF)
  184.                 mark = 0;
  185.             else
  186.             {
  187.                 fseek(fp, -2, SEEK_CUR);
  188.                 previous = fgetc(fp);

  189.                 if(previous == '\n' || previous == '\r')

  190.                     mark = 0;
  191.             }


  192.         }
  193.     }
  194. }
复制代码
回复

使用道具 举报

🔗
EDream 2012-7-22 22:20:19 | 只看该作者
全局:
asterid 发表于 2012-7-22 13:16
按题目要求,将所有节点与source节点的最短路径设为1000000(相当于无穷大)。如果找得到最短路径,距离会 ...

嗯!我最后就是采用这个思路的。
回复

使用道具 举报

🔗
gongluan 2012-7-23 00:32:37 | 只看该作者
全局:
本帖最后由 gongluan 于 2012-7-23 00:34 编辑

这次又偷懒用了 Boost.Graph 库,最近有点忙,等下周有空了把这些算法自己实现一遍

  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <vector>
  5. #include <boost/graph/adjacency_list.hpp>
  6. #include <boost/graph/dijkstra_shortest_paths.hpp>

  7. using namespace std;
  8. using namespace boost;

  9. typedef adjacency_list<vecS, vecS, undirectedS,
  10.                        no_property, property<edge_weight_t, size_t> > graph_t;

  11. int main()
  12. {
  13.     // 定义一个 200 个点的无向图
  14.     graph_t g(200);

  15.     // 读取输入数据,构造无向图
  16.     string line;
  17.     while (getline(cin, line)) {
  18.         // 把每行字符串扔到一个 istringstream 里,便于后面用 >> 提取数据
  19.         istringstream iss(line);
  20.         // 第一列为顶点编号
  21.         size_t v;
  22.         iss >> v;
  23.         // 后面为用 tab 分隔的多对数据,每对又以逗号分隔,
  24.         // 逗号左边为相邻接的顶点,右边为边的权值
  25.         size_t u, weight;
  26.         char comma;
  27.         while (iss >> u >> comma >> weight)
  28.             add_edge(v - 1, u - 1, weight, g);
  29.     }

  30.     // 调用 Dijkstra 算法计算源点到其他所有顶点的最短路径距离
  31.     vector<size_t> distance(num_vertices(g));
  32.     dijkstra_shortest_paths(g, vertex(0, g),
  33.                             distance_map(&distance[0]).
  34.                             distance_inf(1000000));

  35.     // 输出源点到以下这些点的最短路径距离
  36.     size_t targets[] = { 7, 37, 59, 82, 99, 115, 133, 165, 188, 197 };
  37.     for (size_t i = 0; i < sizeof(targets) / sizeof(targets[0]); i++)
  38.         cout << distance[targets[i]-1] << ',';
  39.     cout << endl;
  40.     return 0;
  41. }
复制代码
回复

使用道具 举报

全局:
本帖最后由 蜡笔小丸子 于 2012-7-23 06:31 编辑

没有严格按照老师课上讲的伪代码,而是采用了Dijkstra's Algorithm -wikipedia上的伪代码。顺便问一句:不给加分了么?

  1. #include <iostream>
  2. #include <vector>
  3. #include <fstream>
  4. #include <string>
  5. #include <sstream>
  6. #include <algorithm>
  7. using namespace std;

  8. #define GRAPH_SIZE 200
  9. #define MAX_DIST 1000000

  10. struct Node{
  11.         int dist; // distance from source to node v
  12.         vector<int> adjNode; // v's adjacent nodes
  13.         vector<int> adjNodeDist;  // distance from v to its adjacent nodes
  14.         Node():dist(MAX_DIST){};

  15. };

  16. void ReadFile(char *file, Node Graph[])
  17. {
  18.         ifstream myFile(file);
  19.                 int node=0,adjnode=0,dist=0;
  20.                 if (myFile.is_open()){
  21.                         for (int iNode = 1; iNode<=GRAPH_SIZE; iNode++){
  22.                                 string line;
  23.                                 getline(myFile,line);
  24.                                 stringstream str(line);
  25.                                 str>>node;
  26.                                 if (node == iNode) {
  27.                                         while (str>>adjnode){
  28.                                                 Graph[node-1].adjNode.push_back(adjnode);
  29.                                                 str.ignore();
  30.                                                 str>>dist;
  31.                                                 Graph[node-1].adjNodeDist.push_back(dist);
  32.                                         }
  33.                                 }else
  34.                                         cerr<<"File reading error!"<<endl;
  35.                         }
  36.                 }else cerr<<"Could not open file."<<endl;
  37.                 myFile.close();
  38. }

  39. void Dijkstra(Node Graph[], int sourceNode){
  40.         Graph[sourceNode-1].dist = 0; // distance from source to source

  41.         vector<int> X;   // vertex processed so far

  42.         int alterPath = 0;
  43.         int v,w;
  44.         int min_dist;
  45.         while (X.size()<GRAPH_SIZE){
  46.                 min_dist = MAX_DIST;
  47.                 for (int j=1;j<=GRAPH_SIZE;j++){  //iteration over un-processed nodes w
  48.                         
  49.                         if (find(X.begin(),X.end(),j)!=X.end())
  50.                                 continue;

  51.                         if (Graph[j-1].dist <min_dist){
  52.                                                 // find the unprocessed node w with smallest dist[]
  53.                                 min_dist = Graph[j-1].dist;
  54.                                 w = j;                        
  55.                         }
  56.                 }
  57.                         
  58.                 //if (Graph[w].dist == MAX_DIST) break;
  59.                 X.push_back(w); // add w to X


  60.                 for (vector<int>::size_type k=0;k!=Graph[w-1].adjNode.size();k++){
  61.                         v = Graph[w-1].adjNode.at(k); // for each neighbour v of w
  62.                         alterPath = Graph[w-1].dist + Graph[w-1].adjNodeDist.at(k) ;
  63.                                 if (alterPath <Graph[v-1].dist){
  64.                                                 Graph[v-1].dist = alterPath;
  65.                                                 //Graph[v-1].previous = v;
  66.                                         }
  67.                                 }
  68.         }

  69. }
  70. int main(){

  71.         Node Graph[GRAPH_SIZE];
  72.         
  73.         ReadFile("dijkstraData.txt",Graph);
  74.         
  75.         Dijkstra(Graph,1);

  76.         int textNode[] ={7,37,59,82,99,115,133,165,188,197};
  77.         for (int i=0;i<10;i++){
  78.                 cout<<Graph[textNode[i]-1].dist<<",";
  79.         }
  80.         system("pause");
  81.         return 0;
  82. }
复制代码

回复

使用道具 举报

🔗
modifiedname 2012-8-2 04:07:59 | 只看该作者
全局:
这次的作业好简单,不用heap版:

  1. G={}
  2. f=open('dijkstraData.txt')
  3. for l in f:
  4.     t = l.split()
  5.     lead=int(t[0])
  6.     G[lead]={}
  7.     for each in t[1:]:
  8.         n,w=map(int,each.split(","))
  9.         G[lead][n]=w
  10. f.close()
  11. #print G[6][141] == 8200

  12. ## assume all nodes are reachable from S
  13. def Dijkstra(G,S):
  14.     A=[1000000]*(1+len(G))
  15.     B={}
  16.     for each in G.keys():
  17.         B[each]=[]

  18.     frontier=[S]
  19.     A[S]=0   
  20.     while len(frontier)<len(G): # not all nodes seen
  21.         
  22.         hops = [(A[v]+G[v][w],v,w)
  23.                 for v in frontier
  24.                 for w in G[v].keys()
  25.                 if w not in frontier ]# all edges crossing frontier

  26.         weight,v,w = min(hops)
  27.         frontier.append(w)
  28.         A[w]=weight
  29.         B[w]=B[v]+[(v,w)]
  30.    
  31.     return A,B
  32.         

  33. dist,path= Dijkstra(G,1)
  34. out=[7,37,59,82,99,115,133,165,188,197]
  35. print [dist[i] for i in out]
复制代码

回复

使用道具 举报

🔗
modifiedname 2012-8-2 05:07:44 | 只看该作者
全局:
hehe this week at udacity their algorithm course cs215 is also about dijkstra's....the hw is ONLY to code it up with heap....they gave u the rest of the algorithm already...
but somehow the code is messier
回复

使用道具 举报

🔗
modifiedname 2012-8-4 01:57:36 | 只看该作者
全局:
这用heap和keep track of what's where好像也不是特别trivial啊
有没有自己用python implement heap的筒子?
怎么都通不过udacity grader,嫌不够快
看那边论坛讨论也还没有谁通过了的,做法看了也都差不多啊。。。
回复

使用道具 举报

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

本版积分规则

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