图与最短路径作业

作业

---

第一题

 邻接矩阵

$$\begin{bmatrix} 0&1&0&0&0&1\\ 1&0&1&0&0&0\\ 0&1&0&1&0&1\\ 0&0&1&0&1&0\\ 0&0&0&1&0&1\\ 1&0&1&0&1&0\\ \end{bmatrix}$$

 边长邻接矩阵

$$\begin{bmatrix} 0&4&\infty&\infty&\infty&3\\ 4&0&2&\infty&\infty&\infty\\ \infty&2&0&5&\infty&3\\ \infty&\infty&5&0&2&\infty\\ \infty&\infty&\infty&2&0&3\\ 3&\infty&3&\infty&3&0\\ \end{bmatrix}$$

第二题

  邻接矩阵

$$\begin{bmatrix} 0 & 15 & 10 & \infty & \infty & \infty & \infty\\ 15& 0 & \infty & 6 & \infty & \infty & \infty\\ 10& \infty & 0 & \infty & 4 & \infty & \infty\\ \infty& 6 & \infty & 0 & 4 & \infty & 5\\ \infty& \infty & 4 & 4 & 0 & 2 &\infty \\ \infty& \infty & \infty & \infty & 2 & 0 &6 \\ \infty& \infty & \infty & 5 & \infty & 6 &0 \\ \end{bmatrix}$$

 边长邻接矩阵

$$\begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1& 0 & 0 & 1 & 0 & 0 & 0\\ 1& 0 & 0 & 0 & 1 & 0 & 0\\ 0& 1 & 0 & 0 & 1 & 0 & 1\\ 0& 0 & 1 & 1 & 0 & 1 &0 \\ 0& 0 & 0 & 0 & 1 & 0 &1 \\ 0& 0 & 0 & 1 & 0 & 1 &0 \\ \end{bmatrix}$$

中间略。。

第五题

 邻接矩阵

$$\begin{bmatrix} 0 & 1 & 1 & 0 & 0 & 0 & 0\\ 1& 0 & 1 & 1 & 0 & 0 & 1\\ 1& 1 & 0 & 0 & 1 & 0 & 0\\ 0& 1 & 0 & 0 & 1 & 0 & 1\\ 0& 0 & 1 & 1 & 0 & 1 &0 \\ 0& 0 & 0 & 0 & 1 & 0 &1 \\ 0& 1 & 0 & 1 & 0 & 1 &0 \\ \end{bmatrix}$$

 边长邻接矩阵

$$\begin{bmatrix} 0 & 15 & 10 & \infty & \infty & \infty & \infty\\ 15& 0& 3 & 6 & \infty & \infty & 17\\ 10& 3 & 0& \infty & 4 & \infty & \infty\\ \infty& 6 & \infty & 0& 4 & \infty & 5\\ \infty& \infty & 4 & 4 & 0& 2 &\infty \\ \infty& \infty & \infty & \infty & 2 & 0&6 \\ \infty& 17 & \infty & 5 & \infty & 6 &0 \\ \end{bmatrix}$$

<matlab code>
a= [0 15 10 inf inf inf inf;
    15 0 3 6 inf inf 17;
    10 3 0 inf 4 inf inf;
    inf 6 inf 0 4 inf 5;
    inf inf 4 4 0 2 inf ;
    inf inf inf inf 2 0 6 ;
    inf 17 inf 5 inf 6 0 ;]
G=sparse(a);

[Dist,Path]=graphshortestpath(G,3,5)

结果

Dist =

 4
Path =
    3     5