曙光教育
Witney 老师
任教中数/低数
学历：
-墨尔本大学本科主修工程，辅修数学。
-Master of Teaching(Secondary)。
经历：
-因为出色的学术成绩，数次获得Academic Honours，Academic Excellence Awards.
-高中QCE ATAR分数高达98分，达到昆士兰Top 2
今天讲的是如何运用Dijkstra’s algorithm在matrix中找出最短路径 和spannning tree的定义，分类以及最短路线问题。
1.Dijkstra’s alogorithm
找matrix中最短路径的方法之一，结合例题来解释过程
第一步：创建一个表格 把起始点（S）放在表格的最左边 把其他点放在上方
第二步：把起始点到其他点的长度一次计入表格 若不能直接到达打叉号
并找到最小数（13） 则S-K距离最短 将最短距离13在表格中圈起来 把最小距离相对应的点（K）列入起始点下
第三步：重复上面的步骤计入（K）到其他点的距离
到达终点（T）为止
第四步：反推出最短路径
2.trees
没有loop没有multiple edges没有cycles的matrix我们称之为tree，一个tree的edges永远比vertices少一个。
Spanning tree：首先要满足tree的要求 并连接所有的点
如何计算一个tree的total weight
所有edge的和Minimum spanning tree: 每个matrix都有不同的spanning tree的组合 total weight最小的spanning tree就是 minimum spanning tree
用来算最小值的方法叫 prim’s algorithm:
第一步：选任意一点为初始点
第二步：从初始点出发 选择edge最短的一条路 （如果两条路距离一样则选哪条路都可以）
第三步：继续从两点选择最短路线
第四步：以此类推重复此方法知道连接到了所有vertice
责任编辑/转载：猫叔徐超
Witney
中数/低数
Irene
EAL
Steven
会计Accounting
Elaine
EAL英语
Jay
科学/化学/物理/数学
John
物理/中数/高数
Yuki
VCE日语
Patrick
数学/物理
Cecilia
中文第一语言
James
EAL
* 更多视频关注公众号“曙光VCE”或小红书“墨尔本曙光VCE”
* 更多学术干货关注公众号“曙光VCE”或小红书“墨尔本曙光VCE”
