单源点最短路径算法:Dijkstra算法

背景知识 图简介 图由节点和边组成,边有方向的图称为有向图,边没有方向的图称为无向图,最短路径算法里可以把无向图视为双向连接的有向图。 边有权重的图称为有权图,边没有权重的图称为无权图,无权图可以视为边的权重均为1的图。 单源点最短路径 给定图中的一个节点,求该节点……

阅读全文

单源点最短路径算法:Bellman Ford算法

背景知识 图简介 图由节点和边组成,边有方向的图称为有向图,边没有方向的图称为无向图,最短路径算法里可以把无向图视为双向连接的有向图。 边有权重的图称为有权图,边没有权重的图称为无权图,无权图可以视为边的权重均为1的图。 单源点最短路径 给定图中的一个节点,求该节点……

阅读全文