# 纸上谈兵: 最短路径与贪婪

### 加权网络

• 已知点：已知到达A最短距离的点。“我是成功人士。”
• 邻接点：有从记录点出发的边，直接相邻的点。“和成功人士接触，也有成功的机会哦。”
• 未知点：“还早得很。”

• 当前情况下，从A点出发到达该邻接点的最短距离。比如对于上面的点D，为6。
• 此最短距离下的上游节点。对于上面的点D来说，为A。

• 如果下游节点Q还不是邻接点，那么直接加入，Q最短距离 = 新距离，Q上游节点为X。
• 如果下游节点Q已经是邻接点，记录在册的上游节点为Y，最短距离为y。如果新距离小于y，那么最小距离改为新距离，上游节点也改为X。否则保持原记录不变。

A

0

A

C

1

A

D

6

A

E

9

A

P

A

0

A

C

1

A

D

6

A

E

9

A

P

4

C

A

0

A

C

1

A

D

6

A

E

7

P

P

4

C

A

0

A

C

1

A

D

6

A

E

7

P

P

4

C

### 实现

```/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 5
#define INFINITY 10000

typedef struct node *position;
typedef struct record *label;

/* node */
struct node {
int element;
position next;
int weight;
};

/* table element, keep record */
struct record {
int status;
int distance;
int previous;
};

/*
* operations (stereotype)
*/
void insert_edge(position, int, int, int);
void print_graph(position, int);
int new_neighbors(position, label, int, int);
void shortest_path(position, label, int, int, int);

/* for testing purpose */
void main()
{
struct node graph[NUM_V];
struct record records[NUM_V];
int i;

// initialize the vertices
for(i=0; i<NUM_V; i++) {
(graph+i)->element = i;
(graph+i)->next    = NULL;
(graph+i)->weight  = -1;
}

// insert edges
insert_edge(graph,0,1,1);
insert_edge(graph,0,2,6);
insert_edge(graph,0,3,9);
insert_edge(graph,1,4,3);
insert_edge(graph,4,3,3);

print_graph(graph,NUM_V);

// initialize the book
for (i=0; i<NUM_V; i++){
(records+i)->status   = -1;
(records+i)->distance = INFINITY;
(records+i)->previous = -1;
}

shortest_path(graph, records, NUM_V, 0, 3);

//
}
void shortest_path(position graph, label records, int nv, int start, int end) {
int current;

(records+start)->status   = 1;
(records+start)->distance = 0;
(records+start)->previous = 0;

current = start;
while(current != end) {
current = new_neighbors(graph, records, nv, current);
}

while(current != start) {
printf("%d <- ", current);
current = (records+current)->previous;
}
printf("%d\n", current);
}

int new_neighbors(position graph, label records, int nv, int current) {
int newDist;
int v;
int i;
int d;

position p;

// update the current known
(records + current)->status = 1;

// UPDATE new neighbors
p = (graph+current)->next;
while(p != NULL) {
v = p->element;
(records + v)->status = 0;
newDist = p->weight + (records + current)->distance;
if ((records + v)->distance > newDist) {
(records + v)->distance = newDist;
(records + v)->previous = current;
}
p = p->next;
}

// find the next known
d = INFINITY;
for (i=0; i<nv; i++) {
if ((records + i)->status==0 && (records + i)->distance < d){
d = (records + i)->distance;
v = i;
}
}
return v;
}

/* print the graph */
void print_graph(position graph, int nv) {
int i;
position p;
for(i=0; i<nv; i++) {
p = (graph + i)->next;
printf("From %3d: ", i);
while(p != NULL) {
printf("%d->%d; w:%d ", i, p->element, p->weight);
p = p->next;
}
printf("\n");
}
}

/*
* insert an edge
* with weight
*/
void insert_edge(position graph,int from, int to, int weight)
{
position np;

np = graph + from;

nodeAddr = (position) malloc(sizeof(struct node));
}```

From   0: 0->3; w:9 0->2; w:6 0->1; w:1

From   1: 1->4; w:3

From   2:

From   3:

From   4: 4->3; w:3

3 <- 4 <- 1 <- 0

247 篇文章58 人订阅

0 条评论

## 相关文章

39260

31850

### GPU捉襟见肘还想训练大批量模型？谁说不可以

2018 年的大部分时间我都在试图训练神经网络时克服 GPU 极限。无论是在含有 1.5 亿个参数的语言模型（如 OpenAI 的大型生成预训练 Transfo...

44830

57630

768100

75920

75350

44360

49990

69060