Graph Dijkstra’s algorithm 實作 in JAVA(四)
Graph Terminology:
graph G = (V, E) ，V是vertex的集合，E是edge的集合
其中又分成Directed Graph、Undirected Graph
在Graph中有Cn取2＝n (n — 1)/2種edges可能。
Directed Graph因有方向性，兩vertex之間可互指，所以最多有n (n — 1)條edges。
Undirected Graph 兩vertex之間只有一條，所以最多有n (n — 1)/2條edges。
Edge 表示：
兩Graph之關係表示
Graph Terminology in Data:
Adjacency matrix:
Advantage: O(1) time to find an edge
Drawback: O(|V|^2) space to storage
suitable for dense graphs
Adjacency list:
Advantage: O(|V|+|E|) space to storage
Drawback: need to traverse all list to find an edge
suitable for sparse graphs
Graph with Weighted Edges (Network):
在 Adjacency matrix 預設cost=1，若要加入權重直接更改1為cost值即可。
在 Adjacency list 中，則需要在node 中新增一個Weight值。
Shortest Paths — Single Source All Destinations : Nonnegative Edge Costs :
Dijkstra’s algorithm:
先來看看Dijkstra’s algorithm pseudocode:
DIJKSTRA(G(圖),w(cost),s(累積路徑))
1. INITIALIZE-SINGLE-SOURCE(G,s)初始化source，輸入G(圖)跟s(累積路徑)
2. 初始化S(走過的vertex)為空集合
3. 初始化Q為G的vertex之集合
4. while(Q不等於空集合)
5. u = EXTRACT-MIN(Q) 從Q中找出Shorest為最小之Q的index
6. S = S與{u}的連集
7. for(v in G.adj[u])與u有連結的edge(從u連出去)
8. RELAX(u,v,w)
INITIALIZE-SINGLE-SOURCE(G,s)
1. for(v in G.v) 在G.v中所有的vertex
2. v.d = ∞ 初始到達的cost=無限
3. v.π = NULL v到下一個節點=NULL
4. s.d = 0 累積路徑=0
RELAX(u,v,w) 與u有連結的edge
1. if(到達v的cost > 到達u的cost+u到達v的cost)
2. 原本的cost比較大，所以換成新的cost
3. v的上一個vertex是uJAVA:
如果有錯誤歡迎在下面留言～
或者
給我5下拍手👏，讓我知道你(妳)喜歡
給我10下拍手👏，讚賞我的文章
給我50下拍手👏，回饋是我成長與分享的動力喔💪
