图论模型-Dijkstra算法

1、图论模型-Dijkstra算法主讲人：泰山教育小石老师v1v2v3v4v5v6v7v8v9v10v112817615129341369272149Dijkstra算法简介Dijkstra算法能求一个顶点到另一顶点最短路径。它是由Dijkstra于1959年提出的。实际它能出始点到其它所有顶点的最短路径。Dijkstra算法是一种标号法：给赋权图的每一个顶点记一个数，称为顶点的标号（临时标号，称T标号，或者固定标号，称为P标号）。T标号表示从始顶点到该标点的最短路长的上界；P标号则是从始顶点到该顶点的最短路长。Dijkstra算法步骤如下：Dijkstra算法简介111(1)P()0(2,3,,)T()njjjvdvvjndvl===给顶点标标号，给顶点标标号；000001(2)()()()jjjjjjjjjTdvlvTPTTvTdvdvlvT=+在所有标号中取最小值，譬如，，则把的标号改为标号，并重新计算具有标号的其它各顶点的标号：选顶点的标号与中较小者作为的新的标号。(3)P重复上述步骤，直到目标顶点的标号改为标号。v1v2v3v4v5v6v7v8v9v10v11281761512。

2、9341369272149v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490281∞∞∞∞∞∞∞v1v2v3v4v5v6v7v8v9v10v112817615129341369272149028∞∞10∞∞∞∞1v1v2v3v4v5v6v7v8v9v10v112817615129341369272149083∞10∞∞∞∞12v1v2v3v4v5v6v7v8v9v10v11281761512934136927214908610125∞∞123v1v2v3v4v5v6v7v8v9v10v112817615129341369272149086101214∞1235v1v2v3v4v5v6v7v8v9v10v11281761512934136927214907101214∞12356v1v2v3v4v5v6v7v8v9v10v112817615129341369272149091214∞123567v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901214101235679v1v2v3v4v5v6v7v8。

3、v9v10v11281761512934136927214901114123567910v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901312356791011v1v2v3v4v5v6v7v8v9v10v11281761512934136927214901235679101113泰山教育版权所有淘宝ID:liuxingma123背景v1v2v3v4v5v6v7v8v9v10v112817615129341369272149顺序：1,2,5,6,3,7,10,9,11泰山教育版权所有淘宝ID:liuxingma123带权邻接矩阵带权邻接矩阵：是表示顶点之间相邻关系的矩阵。v1v2v3v4v5v6v7v8v9v10v1128176151293413692721490281InfInfInfInfInfInfInf206Inf1InfInfInfInfInfInf8607512InfInfInfInf1Inf70InfInf9InfInfInfInfInf15Inf03Inf29InfInfInfInf1Inf304Inf6InfInfInfI。

4、nf29Inf40Inf31InfInfInfInfInf2InfInf07Inf9InfInfInfInf9637012InfInfInfInfInfInf1Inf104InfInfInfInfInfInfInf9240泰山教育版权所有淘宝ID:liuxingma123带权邻接矩阵1023741165981351221061588799322708InfInfInfInf78InfInfInfInf03InfInfInfInfInfInfInfInfInfInf056Inf5InfInfInfInfInfInfInf01InfInfInfInfInf12InfInf6Inf02InfInfInfInf10InfInfInfInf209Inf3InfInfInfInfInfInfInf90InfInfInfInf8InfInfInfInfInfInf09InfInfInfInfInfInf7InfInf902InfInfInfInfInfInfInfInfInf202InfInfInfInf10InfInfInfInfInf0。