我想可视化 Dijkstra 算法以找到最短路径。我受到了这个的启发邮政。遗憾的是，我的 LaTeX 水平太差了。我最初的想法是使用 LuaLaTeX 来实现，然后我能够用它编写 Dijkstra 算法：
-- init, graph should the an incidence list, directed a boolean
function dijkstra_initialize(graph, directed, start_node)
-- global variables
graph = graph
current_node = start_node
is_directed = directed
not_visited_nodes = {}
visited_nodes = {}
-- init not visited
for node, _ in pairs(graph) do
table.insert(not_visited_nodes, node)
end
-- init distances
distances = {}
for node, _ in pairs(graph) do
distances[node] = math.huge
end
distances[start_node] = 0
-- init pred
predecessors = {}
for node, _ in pairs(graph) do
predecessors[node] = nil
end
end
function dijkstra_step()
if #not_visited_nodes == 0 then
return
end
local min_distance = math.huge
local next_node
for _, node in ipairs(not_visited_nodes) do
if distances[node] < min_distance then
min_distance = distances[node]
next_node = node
end
end
table.remove(not_visited_nodes, table.indexof(not_visited_nodes, next_node))
table.insert(visited_nodes, next_node)
current_node = next_node
for node, weight in pairs(graph[current_node]) do
local distance = distances[current_node] + weight
if distance < distances[node] then
distances[node] = distance
predecessors[node] = current_node
end
end
end
我不知道这是否有用。我的问题是我不知道如何使用 TikZ 访问 Lua 并可视化变量。我的想法是\dijkstra_initialize()在 LaTeX 中有一个函数来初始化所有内容，\dijkstra_empty_graph该函数用于显示没有访问节点的图形，\dijkstra_empty_table以显示初始空表。此外，我还考虑了一个\dijkstra_step函数来打印下一个图形和表格，该函数以某种颜色显示当前节点，例如红色，以某种颜色显示访问过的节点，不同于未访问节点的颜色。我想，也许有一个函数可以\dijkstra_step_table执行步骤但仅显示表格和\dijkstra_step_graph图形会很有用。最后，我认为有一个\dijkstra_finish \dijkstra_finish_table \dijkstra_finish_graph会很棒，它只需调用相应的步骤函数，直到算法终止。我认为这在 Lua 中如下所示：
function dijkstra_finish()
while #not_visited_nodes > 0 do
dijkstra_step()
end
end
到目前为止，我的图表和表格都是硬编码的，如下所示：
[
如果有人能帮助我，我会非常高兴，因为我已经考虑这个项目有一段时间了，但是我对 LaTeX、TikZ 或 Lua 的了解还不够好。
答案1
这是 TeX 中的 Dijkstra 算法。
它使用 PGFFor (.list处理程序) 和 PGFMath ( \pgfmathloop) 进行循环：
- 这
.list处理程序用于存储每条边的权重并执行所有步骤。 - 该
\pgfmathloop宏（未记录）与 LaTeX 非常相似，\loop但提供了一个额外的计数器\pgfmathcounter（不是 TeX 计数也不是 LaTeX 计数器）。
只需稍加努力，两者便可相互转化。
PGFMath 包还加载了一个小型的未记录的实用程序 PGFInt，它提供的功能几乎是和 L3 的\pgfinteval克隆，我只是用它来代替作为一种更简单的添加两个整数的方法。xfp\inteval\numexpr<int 1>+<int 2>\relax
PGFKeys 包用于主界面，
- 用户界面键
n，steps以及startn是节点数（1，...，n),start是算法应该开始的节点的编号，steps是算法应使用的最大步数；
weight matrix存储（可能有向的）权重矩阵（用于i无穷大）的键；- 内部按键
__init，__step负责完成艰苦的工作； - 一些测试
is calculated = {<i>}{<true>}{<false>}测试到节点的距离我至少已经计算过了（不代表它是平均值，只是意味着邻居已经被访问过了——这不是算法的一部分，但出于可视化的原因我喜欢它），is visited = {<i>}{<true>}{<false>}测试节点我已被访问过，is current = {<i>}{<true>}{<false>}测试是否我是当前节点，即当前步骤的源节点，is edge = {<i>-<j>}{<true>}{<false>}测试边缘我到杰实际上分配了一个不等于无穷大的权重，并且is pred = {<i>}{<j>}{<true>}{<false>}测试是否杰是……的前身我; 和
- 实际上存储了所有的结果（它只是
\csname和的一个奇特的界面\endcsname）。
所有绘图均由 TikZ 完成，这意味着：
- 节点放置
- 节点之间的边和权重
- 使用上述测试的节点风格。
从技术上讲，dijkstra环境仅用于对计算进行分组（因为代码会覆盖自身，以便算法完成时不会进行不必要的迭代，但根据密钥还有更多步骤要做steps）。
除了 TikZ 图表之外，您还可以tabular在其中放置一个。
对于每一步，所有这些计算的距离和前任的快照都会被存储起来，以后可以访问……
这是为tabular下图完成的。（这不需要在 TikZ 图表中，我只是为了这个答案而把它放在那里。）
对于表，使用另一组命令来测试每个节点的特定内容，其中可选的第一个参数是要测试的步骤。（如果没有使用可选参数，则使用算法的“全局”值。）
TFX其中一些测试以（而不是正常的布尔值）结束TF。这些测试检查所需值是否实际存在，如果不存在，则将使用最后一个参数。（例如，在步骤 2 中，步骤 3 及以上的所有值都不存在，因此不应在单元格中写入任何内容。）
就表创建而言，这可能不是解决这个问题的最佳方法。
我特意使用 8 个步骤而不是所需的 5 个或 6 个步骤，以表明如果要求执行比必要更多的步骤，代码不会中断。
是的，初始化阶段是步骤 0，其中只有起始节点被标记为已访问且距离为 0。
代码
\documentclass[tikz]{standalone}
\usepackage{pgfkeys, pgfmath, pgffor}% for dij algo
\usepackage{tikz} % for drawing
\usepackage{booktabs, array} % for nice tabulars
%% User Interface
\newcommand*\dijset{\pgfqkeys{/dij}}
\newenvironment*{dijkstra}[1][]{%
\dijset{#1, __init}%
\ifnum\pgfkeysvalueof{/dij/steps}>0
\dijset{__step/.list/.expanded={1,...,\pgfkeysvalueof{/dij/steps}}}%
\fi}{}
\newcommand*\DijNodeDist[1]{% return the distance to #1 or infty
\ifnum\pgfkeysvalueof{/dij/node #1/dist}<2147483647\relax
\pgfkeysvalueof{/dij/node #1/dist}\else\infty\fi}
\dijset{
weight matrix/.style={
/utils/exec=\def\listrow{0},
/utils/rows/.style={
/utils/exec=\def\listcol{0}%
\edef\listrow{\the\numexpr\listrow+1\relax},
/utils/cols/.ecode={%
\edef\noexpand\listcol{\noexpand\the\numexpr\noexpand\listcol+1\relax}%
\noexpand\if i####1%
\noexpand\pgfkeyssetevalue{/dij/weight/\listrow-\noexpand\listcol}{2147483647}%
\noexpand\else
\noexpand\pgfkeyssetevalue{/dij/weight/\listrow-\noexpand\listcol}{####1}%
\noexpand\fi
},
/utils/cols/.list={##1},
},
/utils/rows/.list={#1}},
start/.initial = 1,
n/.initial = 10,
steps/.initial = 10}
\makeatletter
%% Algorithm
\newif\ifdij@allvisited
\newcommand*{\pgfkeysletlet}[2]{\pgfkeysgetvalue{#2}\pgfkeys@temp\pgfkeyslet{#1}\pgfkeys@temp}
\dijset{
__init/.code={%
\def\dij@nodecurrent{0}% for step = 0
\pgfmathloop
\pgfkeyssetvalue{/dij/node \pgfmathcounter/dist}{2147483647}%
\pgfkeyssetvalue{/dij/node \pgfmathcounter/visited}{0}%
\pgfkeyssetvalue{/dij/node \pgfmathcounter/pred}{0}%
\pgfkeyssetvalue{/dij/node \pgfmathcounter/step 0/dist}{2147483647}%
\pgfkeyssetvalue{/dij/node \pgfmathcounter/step 0/visited}{0}%
\pgfkeyssetvalue{/dij/node \pgfmathcounter/step 0/pred}{0}%
\ifnum\pgfmathcounter<\pgfkeysvalueof{/dij/n}%
\repeatpgfmathloop
\pgfkeyssetvalue{/dij/node \pgfkeysvalueof{/dij/start}/dist}{0}%
\pgfkeyssetvalue{/dij/node \pgfkeysvalueof{/dij/start}/step 0/dist}{0}%
},
__step/.code={%
%% Are all visited?
%% And if not: what's the node with the min distance?
\dij@allvisitedtrue
\def\dij@nodecurrent{0}%
\def\dij@nodedist{2147483647}%
\pgfmathloop
\ifnum\pgfkeysvalueof{/dij/node \pgfmathcounter/visited}=0\relax
\dij@allvisitedfalse
\pgfkeysgetvalue{/dij/node \pgfmathcounter/dist}\dij@temp
\ifnum\dij@temp<\dij@nodedist\relax
\let\dij@nodecurrent\pgfmathcounter
\let\dij@nodedist\dij@temp
\fi
\fi
\ifnum\pgfmathcounter<\pgfkeysvalueof{/dij/n}%
\repeatpgfmathloop
%% Try to visit all neighbours of min node.
\ifdij@allvisited\dijset{__step/.code=}% don't repeat me
\else
\pgfkeyssetvalue{/dij/node \dij@nodecurrent/visited}{1}%
\pgfkeyssetvalue{/dij/node \dij@nodecurrent/step #1/visited}{1}%
\pgfkeyssetvalue{/dij/node \dij@nodecurrent/step #1}{}% mark current node
\pgfmathloop
\ifnum\pgfkeysvalueof{/dij/node \pgfmathcounter/visited}=0\relax % not yet visited
\unless\ifnum\pgfkeysvalueof{/dij/weight/\dij@nodecurrent-\pgfmathcounter}=2147483647\relax
\edef\dij@temp{\pgfinteval{\dij@nodedist+\pgfkeysvalueof{/dij/weight/\dij@nodecurrent-\pgfmathcounter}}}%
\ifnum\dij@temp<\pgfkeysvalueof{/dij/node \pgfmathcounter/dist}\relax
\pgfkeyslet{/dij/node \pgfmathcounter/dist}\dij@temp
\pgfkeyslet{/dij/node \pgfmathcounter/pred}\dij@nodecurrent
\fi
\fi
\fi
\pgfkeysletlet{/dij/node \pgfmathcounter/step #1/dist}{/dij/node \pgfmathcounter/dist}%
\pgfkeysletlet{/dij/node \pgfmathcounter/step #1/pred}{/dij/node \pgfmathcounter/pred}%
\pgfkeysletlet{/dij/node \pgfmathcounter/step #1/visited}{/dij/node \pgfmathcounter/visited}%
\ifnum\pgfmathcounter<\pgfkeysvalueof{/dij/n}%
\repeatpgfmathloop
\fi
}
}
%% Test Keys
\dijset{
@create test 1/.style 2 args={
#1/.code n args={3}{#2\expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi
{\pgfkeysalso{##2}}{\pgfkeysalso{##3}}}},
@create test 2/.style 2 args={
#1/.code n args={4}{#2\expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi
{\pgfkeysalso{##3}}{\pgfkeysalso{##4}}}},
@create test 1={is current}{\ifnum\dij@nodecurrent=#1\relax}}
\makeatother
\dijset{
@create test 1={is visited}{\ifnum\pgfkeysvalueof{/dij/node #1/visited}=1\relax},
@create test 1={is edge}{\ifnum\pgfkeysvalueof{/dij/weight/#1}<2147483647\relax},
@create test 2={is pred}{\ifnum\pgfkeysvalueof{/dij/node #1/pred}=#2\relax},
@create test 1={is calculated}{\ifnum\pgfkeysvalueof{/dij/node #1/dist}<2147483647\relax}
}
%% Table
\dijset{table/.cd,
.style={/dij/table/content/.initial=, /dij/table/row/.list={#1}},
row/.style={%
/dij/table/content/.append={#1},
/dij/table/col/.style={%
/dij/table/content/.append={%
\DijIfNumTF{0=#1}{%
& / & $\DijIsNodeStartTF{##1}{0}{\infty}$
}{%
\DijIsNodeStartTF{##1}{&&}{%
\DijIsNodeCalculatedTFX[#1]{##1}{%
\DijIsNodeVisitedTFX[#1]{##1}{%
\DijIsNodeCurrentTF[#1]{##1}{%
& $\pgfkeysvalueof{/dij/table/node function}
{\pgfkeysvalueof{/dij/node ##1/step #1/pred}}$
& $\pgfkeysvalueof{/dij/node ##1/step #1/dist}$
}{&&}%
}{%
& $\pgfkeysvalueof{/dij/table/node function}
{\pgfkeysvalueof{/dij/node ##1/step #1/pred}}$
& $\pgfkeysvalueof{/dij/node ##1/step #1/dist}$
}{&&}%
}{& / & $\infty$}{&&}%
}%
}%
}%
},
/dij/table/col/.list/.expanded={1,...,\pgfkeysvalueof{/dij/n}},
/dij/table/content/.append=\\}}
%% Tests
\makeatletter
\def\dij@firstofthree#1#2#3{#1}
\def\dij@secondofthree#1#2#3{#2}
\def\dij@thirdofthree#1#2#3{#3}
\dijset{table/node function/.initial=\@Alph}
\def\dij@teststep#1{\ifnum#1<0 \else step #1/\fi}
\newcommand*\dij@relaxTF[3]{%
\pgfkeysgetvalue{/dij/node #2/\dij@teststep{#1}#3}\dij@temp
\ifx\dij@temp\relax\expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi}
\newcommand*\DijIsNodeVisitedTFX[2][-1]{%
\dij@relaxTF{#1}{#2}{visited}{\dij@thirdofthree}{%
\ifnum\dij@temp=1\relax
\expandafter\dij@firstofthree\else\expandafter\dij@secondofthree\fi}}
\newcommand*\DijIsNodeCalculatedTFX[2][-1]{%
\dij@relaxTF{#1}{#2}{dist}{\dij@thirdofthree}{%
\ifnum\dij@temp<2147483647\relax
\expandafter\dij@firstofthree\else\expandafter\dij@secondofthree\fi}}
\newcommand*\DijIsNodeStartTF[1]{\ifnum\pgfkeysvalueof{/dij/start}=#1\relax
\expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi}
\newcommand*\DijIfNumTF[1]{%
\ifnum#1\relax\expandafter\@firstoftwo\else\expandafter\@secondoftwo\fi}
\newcommand*\DijIsNodeCurrentTF[2][-1]{%
\dij@relaxTF{#1}{#2}{}{\@secondoftwo}{\@firstoftwo}}
\makeatother
\begin{document}
\dijset{
n = 6, start = 1,
weight matrix={
{0,6,5,i,i,i},
{6,0,7,1,i,i},
{5,7,0,8,4,i},
{i,1,8,0,9,2},
{i,i,4,9,0,3},
{i,i,i,2,3,0}}}
\foreach \STEP in {0,...,8}{%
\begin{dijkstra}[steps = \STEP]
\begin{tikzpicture}[
thick, scale=2,
node edge 1-2/.style=swap,
node edge 4-6/.style=swap,
]
\foreach[count=\i]\p in {(0,0), (1,1), (1,-1), (3,1), (3,-1), (4,0)}
\node[draw=blue, circle, text width=width("$\infty$"), align=center,
/dij/is calculated={\i}{fill=yellow!25}{},
/dij/is visited={\i}{fill=green}{},
/dij/is current={\i}{fill=yellow}{},
] (\i) at \p
{\begin{tabular}{@{}c@{}} \pgfkeysvalueof{/dij/table/node function}{\i} \\
$\DijNodeDist{\i}$\end{tabular}}
\ifnum\i>1 % there's no possible neighbour for the first node
foreach[expand list] \j in {1,...,\pgfinteval{\i-1}}{
[/dij/is edge={\j-\i}{insert path={
(\i) edge[/dij/is pred={\i}{\j}{}{/dij/is pred={\j}{\i}{}{gray}}]
node[auto, node edge \j-\i/.try]{\pgfkeysvalueof{/dij/weight/\j-\i}}
(\j)}}{}]
}
\fi;
\node[anchor = north west] at (current bounding box.north west) {Step: \STEP};
\small
\node[below=+.5em, inner sep=+0pt] at (current bounding box.south) {%
\pgfmathsetlengthmacro\dijcolleft{width("$M$")}%
\pgfmathsetlengthmacro\dijcolright{width("$00$")}%
\begin{tabular}{r *6{>{\centering \arraybackslash}p{\dijcolleft}
>{\raggedleft\arraybackslash}p{\dijcolright}}}
\toprule
& \multicolumn{2}{c}{$A$} & \multicolumn{2}{c}{$B$} & \multicolumn{2}{c}{$C$}
& \multicolumn{2}{c}{$D$} & \multicolumn{2}{c}{$E$} & \multicolumn{2}{c}{$F$} \\
\cmidrule(lr){2-3}\cmidrule(lr){4-5} \cmidrule(lr){6-7}
\cmidrule(lr){8-9}\cmidrule(lr){10-11}\cmidrule(lr){12-13}
\dijset{table={0,...,8}}%
\pgfkeysvalueof{/dij/table/content}%
\bottomrule
\end{tabular}
};
\end{tikzpicture}
\end{dijkstra}}
\end{document}
输出
