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
|
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta name="generator" content=
"HTML Tidy for Linux/x86 (vers 1st December 2004), see www.w3.org" />
<meta http-equiv="Content-Type" content="text/html; charset=big5" />
<link rel="stylesheet" href="../../c/exam.css" type="text/css" />
<title>ɧU algotutor s@pҽd</title>
</head>
<body>
<h1>ɧU algotutor s@pҽd</h1>
<hr />
<p>Algotutor ЮvXD]ܦUC ЮviH gen_at_graph
ͤ@ӫܤjüƹ, bYӺtki@bɭ,
߰ݾǥͤU@B|oͤơC pGnζDzΤu覡o,
įqoӧCC HUҤlNO@̥ algotutor
һs@pҦD@C</p>
<hr />
<p>Ϥ@: <img src="q61.png" alt="Ϥ@" /></p>
<p>ϤG: <img src="q62.png" alt="ϤG" /></p>
<ol>
<li>Ϥ@O Dijkstra's algorithm for single source shortest path
problem i@bɪpC UӭnN L q Fringe X, ⥦ܦ
visitedC а L CӾF~ (F parent ~) |ܤ?
<ul>
<li>__ A; ____ @ back edge;</li>
<li>__ q unseen ܦ fringe, value __;</li>
<li>__ parent q __ ܦ __, value q __ ܦ __</li>
<li>...</li>
</ul>
</li>
<li>~i, SϤGC H q fringe ܦ visited,
ҦF~uѤU I ٨SBz, heap e: W 8, C 9, P 13, U
11, N 10, I 14, S 13, Q 11 @ 8 ӤC дyzBz I , graph
P heap U|oͤܤ?</li>
<li> <a href="q63.gr">@ graph</a> i Prim's algorithm إ
minimal spanning treeC q G Xo; i@bɩϤTC ɪ
heap e: S 1, J 2, W 4, E 3, O 2, L 8, A 4, R 8, M 3, B 7 @ 10
ӤC {bYNq fringe X S, Nܦ visitedC еeX
uX Sv e, heap e, ýмХܥXW/U|C</li>
<li>ЦCX S C neighbor (F parent ~) ܤ:
<ul>
<li>__ A; ____ @ back edge;</li>
<li>__ q unseen ܦ fringe, value __;</li>
<li>__ parent q __ ܦ __, value q __ ܦ __</li>
<li>... </li>
</ul>
</li>
</ol>
<p>ϤT: <img src="q63.png" alt="ϤT" /></p>
</body>
</html>
|
