forked from yourtion/LearningMasteringAlgorithms-C
-
Notifications
You must be signed in to change notification settings - Fork 0
/
shortest.c
152 lines (100 loc) · 3.17 KB
/
shortest.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//
// shortest.c
// Algorithms - Shortest paths (Dijkstra)
//
// Created by YourtionGuo on 24/05/2017.
// Copyright © 2017 Yourtion. All rights reserved.
//
#include <float.h>
#include <stdlib.h>
#include "graph.h"
#include "graphalg.h"
#include "list.h"
#include "set.h"
#pragma mark - Private
/**
释放所选顶点与相邻顶点间的边
@param u 顶点 1
@param v 顶点 2
@param weight 权重
*/
static void relax(PathVertex *u, PathVertex *v, double weight)
{
/// 释放顶点 u 和 v 之间的边
if (v->d > u->d + weight) {
v->d = u->d + weight;
v->parent = u;
}
return;
}
#pragma mark - Public
int shortest(Graph *graph, const PathVertex *start, List *paths,
int (*match)(const void *key1, const void *key2))
{
AdjList *adjlist = NULL;
PathVertex *pth_vertex, *adj_vertex;
ListElmt *element, *member;
double minimum;
int found, i;
/// 初始化图的所有顶点
found = 0;
for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) {
pth_vertex = ((AdjList *)list_data(element))->vertex;
if (match(pth_vertex, start)) {
/// 初始化起点
pth_vertex->color = white;
pth_vertex->d = 0;
pth_vertex->parent = NULL;
found = 1;
} else {
/// 初始化起点外的其他顶点
pth_vertex->color = white;
pth_vertex->d = DBL_MAX;
pth_vertex->parent = NULL;
}
}
/// 如果找不到起点返回 -1
if (!found) return -1;
/// 使用 Dijkstra 算法计算最短路径
i = 0;
while (i < graph_vcount(graph)) {
/// 选择最短路径的白色顶点
minimum = DBL_MAX;
for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) {
pth_vertex = ((AdjList *)list_data(element))->vertex;
if (pth_vertex->color == white && pth_vertex->d < minimum) {
minimum = pth_vertex->d;
adjlist = list_data(element);
}
}
/// 将选中的顶点涂为黑色
((PathVertex *)adjlist->vertex)->color = black;
/// 遍历选中顶点的每个邻接顶点
for (member = list_head(&adjlist->adjacent); member != NULL; member = list_next(member)) {
adj_vertex = list_data(member);
/// 通过顶点的邻接表找到邻接顶点
for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) {
pth_vertex = ((AdjList *)list_data(element))->vertex;
if (match(pth_vertex, adj_vertex)) {
/// 释放邻接表中的邻接顶点
relax(adjlist->vertex, pth_vertex, adj_vertex->weight);
}
}
}
/// 准备选择下一个顶点
i++;
}
/// 将最短路径载入列表
list_init(paths, NULL);
for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element)) {
/// 从邻接表中加载每个黑色顶点
pth_vertex = ((AdjList *)list_data(element))->vertex;
if (pth_vertex->color == black) {
if (list_ins_next(paths, list_tail(paths), pth_vertex) != 0) {
list_destroy(paths);
return -1;
}
}
}
return 0;
}