圖論最短路徑問題（一）

 圖的基本概念

總概念：圖論中的圖是由若幹給定的點及連接配接兩點的線構成的圖形，表示事物之間的特定關系

點：表示事物

線：表示相應兩個事物之間具有某種的特定關系

• 邊是否有方向：分為有向圖（無向圖的特例）和無向圖
• 邊上是否有權值：分為有權圖和無權圖

線上作圖網站

MATLAB作圖

無向圖制作

無權重

%% Matlab作無向圖
% （1）無權重（每條邊的權重預設為1）
% 函數graph(s,t)，s和t表示對應的結點
% s 和 t 都必須具有相同的維數
% 這些節點必須都是從1開始的連續的正整數
s1 = [1,2,3,4];
t1 = [2,3,1,1];
G1 = graph(s1, t1);
plot(G1)

% 字元串元胞數組用大括号包
s2 = {'學校','電影院','網吧','酒店'};
t2 = {'電影院','酒店','酒店','KTV'};
G2 = graph(s2, t2);
plot(G2)

% 不顯示坐标
set( gca, 'XTick', [], 'YTick', [] );        

有權重

% 可在s和t中的對應節點之間以w的權重建立邊
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = graph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight)   %調用權重的标簽      

有向圖制作

% 無權圖 digraph(s,t)
s = [1,2,3,4,1];
t = [2,3,1,1,4];
G = digraph(s, t);
plot(G)  

% 有權圖 digraph(s,t,w)
s = [1,2,3,4];
t = [2,3,1,1];
w = [3,8,9,2];
G = digraph(s, t, w);
plot(G, 'EdgeLabel', G.Edges.Weight)         

權重鄰接矩陣

無向圖

• 無向圖對應的權重鄰接矩陣是對稱矩陣
• 主對角線元素為0
• 表示第i個節點到第j個節點的權重

有向圖

• 有向圖對應的權重鄰接矩陣不一定是對稱矩陣
• 主對角線元素為0
• 表示第i個節點到第j個節點的權重