第七十八课最短路径（Dijkstra）

核心思想是从已知的最短路径推算未知的最短路径。

添加程序：

  1 #ifndef GRAPH_H
  2 #define GRAPH_H
  3 
  4 #include "Object.h"
  5 #include "SharedPointer.h"
  6 #include "Array.h"
  7 #include "DynamicArray.h"
  8 #include "LinkQueue.h"
  9 #include "LinkStack.h"
 10 #include "Sort.h"
 11 
 12 namespace DTLib
 13 {
 14 
 15 template < typename E >
 16 struct Edge : public Object
 17 {
 18     int b;
 19     int e;
 20     E data;
 21 
 22     Edge(int i=-1, int j=-1)
 23     {
 24         b = i;
 25         e = j;
 26     }
 27 
 28     Edge(int i, int j, const E& value)
 29     {
 30         b = i;
 31         e = j;
 32         data = value;
 33     }
 34 
 35     bool operator == (const Edge<E>& obj)
 36     {
 37         return (b == obj.b) && (e == obj.e);  //在这里不关注权值大小
 38     }
 39 
 40     bool operator != (const Edge<E>& obj)
 41     {
 42         return !(*this == obj);
 43     }
 44 
 45     bool operator < (const Edge<E>& obj)
 46     {
 47         return (data < obj.data);
 48     }
 49 
 50     bool operator > (const Edge<E>& obj)
 51     {
 52         return (data > obj.data);
 53     }
 54 };
 55 
 56 template < typename V, typename E >
 57 class Graph : public Object
 58 {
 59 protected:
 60     template < typename T >
 61     DynamicArray<T>* toArray(LinkQueue<T>& queue)
 62     {
 63         DynamicArray<T>* ret = new DynamicArray<T>(queue.length());
 64 
 65         if( ret != NULL )
 66         {
 67             for(int i=0; i<ret->length(); i++, queue.remove())
 68             {
 69                 ret->set(i, queue.front());
 70             }
 71         }
 72         else
 73         {
 74             THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create ret object...");
 75         }
 76 
 77         return ret;
 78     }
 79 
 80     SharedPointer< Array<Edge<E> > > getUndirectedEdges()
 81     {
 82         DynamicArray<Edge<E>>* ret = NULL;
 83 
 84         if( asUndirected() )
 85         {
 86             LinkQueue<Edge<E>> queue;
 87 
 88             for(int i=0; i<vCount(); i++)
 89             {
 90                 for(int j=i; j<vCount(); j++)
 91                 {
 92                     if( isAdjacent(i, j) )
 93                     {
 94                         queue.add(Edge<E>(i, j, getEdge(i, j)));
 95                     }
 96                 }
 97             }
 98 
 99             ret = toArray(queue);
100         }
101         else
102         {
103             THROW_EXCEPTION(InvalidOperationException, "This function is for undirected graph only...");
104         }
105 
106         return ret;
107     }
108 
109     int find(Array<int>& p, int v)
110     {
111         while( p[v] != -1)
112         {
113             v = p[v];
114         }
115 
116         return v;
117     }
118 public:
119     virtual V getVertex(int i) = 0;
120     virtual bool getVertex(int i, V& value) = 0;
121     virtual bool setVertex(int i, const V& value) = 0;
122     virtual SharedPointer< Array<int> > getAdjacent(int i) = 0;
123     virtual bool isAdjacent(int i, int j) = 0;
124     virtual E getEdge(int i, int j) = 0;
125     virtual bool getEdge(int i, int j, E& value) = 0;
126     virtual bool setEdge(int i, int j, const E& value) = 0;
127     virtual bool removeEdge(int i, int j) = 0;
128     virtual int vCount() = 0;
129     virtual int eCount() = 0;
130     virtual int OD(int i) = 0;
131     virtual int ID(int i) = 0;
132 
133     virtual int TD(int i)
134     {
135         return ID(i) + OD(i);
136     }
137 
138     bool asUndirected()
139     {
140         bool ret = true;
141 
142         for(int i=0; i<vCount(); i++)
143         {
144             for(int j=0; j<vCount(); j++)
145             {
146                 if( isAdjacent(i, j) )
147                 {
148                     ret = ret && isAdjacent(j, i) && (getEdge(i, j) == getEdge(j, i));
149                 }
150             }
151         }
152 
153         return ret;
154     }
155 
156     SharedPointer< Array< Edge<E > > > prim(const E& LIMIT, const bool MINIUM = true) //参数为理论上的最大权值
157     {
158         LinkQueue< Edge<E> > ret;
159 
160         if( asUndirected() )
161         {
162             DynamicArray<int> adjVex(vCount());
163             DynamicArray<bool> mark(vCount());
164             DynamicArray<E> cost(vCount());
165             SharedPointer< Array<int> > aj = NULL;
166             bool end = false;
167             int v = 0;
168 
169             for(int i=0; i<vCount(); i++)
170             {
171                 adjVex[i] = -1;
172                 mark[i] = false;
173                 cost[i] = LIMIT;
174             }
175 
176             mark[v] = true;
177 
178             aj = getAdjacent(v);
179 
180             for(int j=0; j<aj->length(); j++)
181             {
182                 cost[(*aj)[j]] = getEdge(v, (*aj)[j]);
183                 adjVex[(*aj)[j]] = v;
184             }
185 
186             for(int i=0; (i<vCount()) && !end; i++)
187             {
188                 E m = LIMIT;
189                 int k = -1;
190 
191                 for(int j=0; j<vCount(); j++)
192                 {
193                     if( !mark[j] && (MINIUM ? (cost[j] < m) : (cost[j] > m)))
194                     {
195                         m = cost[j];
196                         k = j;
197                     }
198                 }
199 
200                 end = (k == -1);
201 
202                 if( !end )
203                 {
204                     ret.add(Edge<E>(adjVex[k], k, getEdge(adjVex[k], k)));
205 
206                     mark[k] = true;
207 
208                     aj = getAdjacent(k);
209 
210                     for(int j=0; j<aj->length(); j++)
211                     {
212                         if( !mark[(*aj)[j]] && (MINIUM ? (getEdge(k, (*aj)[j]) < cost[(*aj)[j]]) : (getEdge(k, (*aj)[j]) > cost[(*aj)[j]])) )
213                         {
214                             cost[(*aj)[j]] = getEdge(k, (*aj)[j]);
215                             adjVex[(*aj)[j]] = k;
216                         }
217                     }
218                 }
219             }
220         }
221         else
222         {
223             THROW_EXCEPTION(InvalidOperationException, "Prim operator is for undirected graph only...");
224         }
225 
226         if( ret.length() != (vCount() - 1) )
227         {
228             THROW_EXCEPTION(InvalidOperationException, "No enough edge for prim operation...");
229         }
230 
231         return toArray(ret);
232     }
233 
234     SharedPointer< Array<Edge<E> > > kruskal(const bool MINMUM = true)
235     {
236         LinkQueue< Edge<E> > ret;
237 
238         SharedPointer< Array< Edge<E> > > edges = getUndirectedEdges();
239 
240         DynamicArray<int> p(vCount()); //前驱标记数组
241 
242         for(int i=0; i<p.length(); i++)
243         {
244             p[i] = -1;
245         }
246 
247         Sort::Shell(*edges, MINMUM);
248 
249         for(int i=0; (i<edges->length()) && (ret.length() < (vCount() - 1)); i++)
250         {
251             int b = find(p, (*edges)[i].b);
252             int e = find(p, (*edges)[i].e);
253 
254             if( b != e )
255             {
256                 p[e] = b;
257 
258                 ret.add((*edges)[i]);
259             }
260         }
261 
262         if( ret.length() != (vCount() - 1) )
263         {
264             THROW_EXCEPTION(InvalidOperationException, "No enough edges for Kruskal operation...");
265         }
266 
267         return toArray(ret);
268     }
269 
270     SharedPointer< Array<int> > BFS(int i)
271     {
272         DynamicArray<int>* ret = NULL;
273 
274         if( (0 <= i) && (i < vCount()) )
275         {
276             LinkQueue<int> q;
277             LinkQueue<int> r;
278             DynamicArray<bool> visited(vCount());
279 
280             for(int i=0; i<visited.length(); i++)
281             {
282                 visited[i] = false;
283             }
284 
285             q.add(i);
286 
287             while( q.length() > 0 )
288             {
289                 int v = q.front();
290 
291                 q.remove();
292 
293                 if( !visited[v] )
294                 {
295                     SharedPointer< Array<int> > aj = getAdjacent(v);
296 
297                     for(int j=0; j<aj->length(); j++)
298                     {
299                         q.add((*aj)[j]);
300                     }
301 
302                     r.add(v);
303 
304                     visited[v] = true;
305                 }
306             }
307 
308             ret = toArray(r);
309         }
310         else
311         {
312             THROW_EXCEPTION(InvalidParameterException, "Index i is invalid...");
313         }
314 
315         return ret;
316     }
317 
318     SharedPointer< Array<int> > DFS(int i)
319     {
320         DynamicArray<int>* ret = NULL;
321 
322         if( (0 <= i) && (i < vCount()) )
323         {
324             LinkStack<int> s;
325             LinkQueue<int> r;
326             DynamicArray<bool> visited(vCount());
327 
328             for(int j=0; j<visited.length(); j++)
329             {
330                 visited[j] = false;
331             }
332 
333             s.push(i);
334 
335             while( s.size() > 0 )
336             {
337                 int v = s.top();
338 
339                 s.pop();
340 
341                 if( !visited[v] )
342                 {
343                     SharedPointer< Array<int> > aj = getAdjacent(v);
344 
345                     for(int j=aj->length() - 1; j>=0; j--)
346                     {
347                         s.push((*aj)[j]);
348                     }
349 
350                     r.add(v);
351 
352                     visited[v] = true;
353                 }
354             }
355 
356             ret = toArray(r);
357         }
358         else
359         {
360             THROW_EXCEPTION(InvalidParameterException, "Index i is invalid...");
361         }
362 
363         return ret;
364     }
365 
366     SharedPointer<Array<int>> dijkstra(int i, int j, const E& LIMIT)
367     {
368         LinkQueue<int> ret;
369 
370         if( (0 <= i) && (i < vCount()) && (0 <= j) && (j < vCount()) )
371         {
372             DynamicArray<E> dist(vCount());
373             DynamicArray<int> path(vCount());
374             DynamicArray<bool> mark(vCount());
375 
376             for(int k=0; k<vCount(); k++)
377             {
378                 mark[k] = false;
379                 path[k] = -1;
380 
381                 dist[k] = isAdjacent(i, k) ? (path[k] = i, getEdge(i, k)) : LIMIT;
382             }
383 
384             mark[i] = true;
385 
386             for(int k=0; k<vCount(); k++)
387             {
388                 E m = LIMIT;
389                 int u = -1;
390 
391                 for(int w=0; w<vCount(); w++)
392                 {
393                     if( !mark[w] && (dist[w] < m) )
394                     {
395                         m = dist[w];
396                         u = w;
397                     }
398                 }
399 
400                 if( u == -1 )
401                 {
402                     break;
403                 }
404 
405                 mark[u] = true;
406 
407                 for(int w=0; w<vCount(); w++)
408                 {
409                     if( !mark[w] && isAdjacent(u, w) && (dist[u] + getEdge(u, w) < dist[w]) )
410                     {
411                         dist[w] = dist[u] + getEdge(u, w);
412                         path[w] = u;
413                     }
414                 }
415             }
416 
417             LinkStack<int> s;
418 
419             s.push(j);
420 
421             for(int k=path[j]; k != -1; k=path[k])
422             {
423                 s.push(k);
424             }
425 
426             while( s.size() > 0 )
427             {
428                 ret.add(s.top());
429 
430                 s.pop();
431             }
432         }
433         else
434         {
435             THROW_EXCEPTION(InvalidParameterException, "Index<i, j> is invalid...");
436         }
437 
438         if( ret.length() < 2 )
439         {
440             THROW_EXCEPTION(ArithmeticException, "There is no path grom i to j...");
441         }
442 
443         return toArray(ret);
444     }
445 };
446 
447 }
448 
449 #endif // GRAPH_H

测试程序如下：

 1 #include <iostream>
 2 #include "MatrixGraph.h"
 3 #include "ListGraph.h"
 4 
 5 using namespace std;
 6 using namespace DTLib;
 7 
 8 template< typename V, typename E >
 9 Graph<V, E>& GraphEasy()
10 {
11     static MatrixGraph<4, V, E> g;
12 
13     g.setEdge(0, 1, 1);
14     g.setEdge(0, 2, 3);
15     g.setEdge(1, 2, 1);
16     g.setEdge(1, 3, 4);
17     g.setEdge(2, 3, 1);
18 
19     return g;
20 }
21 
22 template< typename V, typename E >
23 Graph<V, E>& GraphComplex()
24 {
25     static ListGraph<V, E> g(5);
26 
27     g.setEdge(0, 1, 10);
28     g.setEdge(0, 3, 30);
29     g.setEdge(0, 4, 100);
30 
31     g.setEdge(1, 2, 50);
32 
33     g.setEdge(2, 4, 10);
34 
35     g.setEdge(3, 2, 20);
36     g.setEdge(3, 4, 60);
37 
38     return g;
39 }
40 
41 int main()
42 {
43     Graph<int, int>& g = GraphComplex<int, int>();
44     SharedPointer< Array<int> > p = g.dijkstra(0, 4, 65535);
45 
46     for(int i=0; i<p->length(); i++)
47     {
48         cout << (*p)[i] << " ";
49     }
50 
51     cout << endl;
52 
53     return 0;
54 }

结果如下：

小结：

第七十八课 最短路径（Dijkstra）

第七十八课最短路径（Dijkstra）