\documentclass[UTF8]{ctexart}
\usepackage[ruled, linesnumbered]{algorithm2e}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{boxedminipage}
\usepackage{circuitikz}
\usepackage{fancyhdr}
\usepackage{float}
\usepackage{fullpage}
\usepackage{gensymb}
\usepackage{geometry}
\usepackage{graphicx}
\usepackage{hyperref}
\usepackage{interval}
\usepackage{listings}
\usepackage{mflogo}
\usepackage{multirow}
\newcommand{\nop}[1]{}
\usepackage{siunitx}
\usepackage{subfigure}
\usepackage{texnames}
\usepackage{textcomp}
\usepackage{tikz}
\usepackage{titlesec}
\usepackage{wrapfig}
\usepackage{xcolor}
\usepackage{xltxtra}

\geometry{left=2.5cm,right=2.5cm,headsep=1cm,bottom=2cm,footnotesep=2cm,headheight=13pt}
\pagestyle{fancy}
\fancyfoot[C]{\thepage}
\fancyhead[L]{计算机科学与技术系}
\fancyhead[C]{\ \ \ \ \ \ \ \ }
\fancyhead[R]{\ \ \ \ \ \ \ \ \ \ \ \ 2023年5月5日}

\ctexset{
    section={
      format+ = \Large \raggedright,
     }
}

\newtheorem{theorem}{定理}
\newtheorem{lemma}{引理}
\newtheorem{definition}{定义}

\parindent0mm
%\pagestyle{empty}

\usetikzlibrary{automata, positioning, arrows}

\newcounter{aufgc}
\newenvironment{example}[1]%
{\refstepcounter{aufgc}\textbf{例题1.\arabic{aufgc}} \emph{#1} \\}
{\vspace{0.2cm}}%

\renewcommand{\labelenumi}{(\alph{enumi})}

\lstset{basicstyle=\ttfamily}

\begin{document}

\section*{所有点对的最短路径}

有向图，有$n(n-1)$个点对，考虑有负权边的情况，假如对每个点调用Bellman-ford算法
则可以在时间复杂度$O(n^2m)$解决这个问题

而我们可以将这个时间复杂度降低

\section*{Floyd-Warshall算法}

时间复杂度为$O(n^3)$，更适用于稠密图

最基本的想法是给出$d^l(i,j)$表示在不大于$l$条边的从点$i$到点$j$的最短路，则有\[d^l(i,j)=\min_{(k,j)\in E}\{d^{l-1}(i,k)+w(k,j)\}\]

另一种递归的思路是\[d^k(i,j)=\begin{cases}
        w(i,j)                                                    & k=0          \\
        \min\left\{d^{k-1}(i,j),d^{k-1}(i,k)+d^{k-1}(k,j)\right\} & k\geqslant 1
    \end{cases}\]

只需要将$k$的循环放在外面，就可以省去上标的问题，空间可以节省下来

其伪代码如下

\begin{algorithm}
    \caption{Floyd-Warshall}
    \SetKw{kwand}{and}
    \ForAll{$i$ \kwand $j$}{
        $d(i,j)=w(i,j)$
    }
    \For{$k=1,\ldots,n$}{
        \For{$i=1,\ldots,n$}{
            \For{$j=1,\ldots,n$}{
                $d(i,j)=\min\{d(i,j),d(i,k)+d(k,j)\}$}
        }
    }
\end{algorithm}

\section*{Johnson算法}

时间复杂度为$O(nm\log n)$，更适用于稀疏图

考虑引入一个势能函数$h:V\to \mathbb{R}$，使得$\hat{w}(i,j)=w(i,j)+h(i)-h(j)\geqslant 0$对所有点对$(i,j)$恒成立.

为了防止有些点对没有联通，考虑加入一个源$s$，其和每个点连一条边，权设为$0$，对这个图进行Bellman-Ford算法，如果没有负圈，则令$h(i)=d(s,i)$，之后对权为$\hat{w}$的图使用Dijkstra算法即可.

\section*{利用矩阵乘法加快算法}

回忆之前的$d^2(i,j)=\min\{d^1(i,j)+d^1(k,j)\}$，如果可以引入运算$\odot,\oplus$，则可以化为$A^{(2)}=A^{(1)}\odot A^{(1)}$

使用矩阵乘法可以判断无向无权图的最短路径：$d(i,j)=\arg\min_l\{A^l(i,j)>0\}$，这也可以使用二分查找，找到$A^{2^k-1}>0$和$A^{2^{k-1}}=0$

\section*{最小生成树}

一些性质：图上唯一最小权的边一定在最小生成树上，而如果有多条最小权的边，每条边都包含在某个最小生成树上

\end{document}
