---
# System prepended metadata

title: 演算法作業4
tags: [algorithm, learning, neopolitan]

---

###### tags: `learning` `algorithm` `neopolitan`

# 演算法作業4
最短路徑實作: 參考學校校區平面圖，選取至少20個景點，設計一個最短路徑搜尋系統。

輸入範例：

2 (野聲樓)

31 (伯達樓)

輸出：

野聲樓到伯達樓的最短路徑及距離

## Source of Map
http://www.fju.edu.tw/file/upload/flatVersion_Original.jpg
![](https://i.imgur.com/qgFEOXe.jpg)
### 
Points 1 ~ 23 are possible points as starting points or destination points.
0, 24, 25, 26 are not points of interest. They are transportation hubs.

## Distance Matrix
Turn a FJU map into a distance matrix.
27 by 27.
Indexing from 0 to 26.
https://github.com/y56/fju-algorithm-hw4-fju-campus-path/blob/master/fju-distance-matrix.csv

## Floyd Algorithm
Input distance matrix
Output matrix P and matrix D
https://github.com/y56/fju-algorithm-hw4-fju-campus-path/blob/master/floyd.py

## Shortest Path and Its Distance
Input matrix P, matrix D, a starting node and a destination node
Output all intermediate nodes on the shortest path and its distance.
https://github.com/y56/fju-algorithm-hw4-fju-campus-path/blob/master/path.py