图算法

chavesgu 发布于2019-08-19 10:29 / 3016人阅读

摘要：最小距离相关算法算法单源最短路径算法路径大于零定义概览迪杰斯特拉算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。注意该算法要求图中不存在负权边。算法可视化代码

最小距离相关算法 Dijkstra算法单源最短路径算法路径大于零 1.定义概览

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。（单源最短路径）

2.算法步骤 2.1 算法思想

首先初始整个带权重的有向图G=(N,E).然后在将所有节点分成两个集合 S(表示已经算计完毕的节点，初始为发起节点，值为0)、U(表示未确定的节点列表，初始为除了初始节点之外的节点，值为无限大)。按照最短路径从U里面的节点移动到S里面，必须保证U中的任意节点到原始节点的距离大于S中的任意节点到原始节点的距离。

2.2 算法步骤

初始化图，u为原始节点、S为已处理节点{u=0}、U未处理节点{除了u其它节点=无限大}。将u设置为当前节点`u

遍历U里面所有节点到`u 距离`d，如果节点不与`u直连则`为无限大。判断U里面的每个节点当前距离是否大于 `d + `u到u的距离，大于就替换

选择U里面节点的距离最小的节点，移动到S。并将其设置为 `u

重复2，3 两个步骤，直到计算完所有节点。

2.3 算法可视化

3.代码 3.1 java + guava

import com.google.common.graph.ImmutableValueGraph;
import com.google.common.graph.MutableValueGraph;
import com.google.common.graph.ValueGraphBuilder;
import lombok.extern.slf4j.Slf4j;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Optional;

@Slf4j
public class DijkstraTest {
    public static void main(String[] args) {
        // init
        MutableValueGraph init = ValueGraphBuilder.undirected().build();

        init.putEdgeValue(1, 2, 7);
        init.putEdgeValue(2, 3, 10);
        init.putEdgeValue(1, 3, 9);
        init.putEdgeValue(1, 6, 14);
        init.putEdgeValue(2, 4, 15);
        init.putEdgeValue(3, 6, 2);
        init.putEdgeValue(3, 4, 11);
        init.putEdgeValue(6, 5, 9);
        init.putEdgeValue(5, 4, 6);
        ImmutableValueGraph graph = ImmutableValueGraph.copyOf(init);


        //1.
        Map S = new HashMap<>();
        Map U = new HashMap<>();
        int u = 1;
        S.put(1, 0);
        for (int i = 2; i <= 6; i++) {
            U.put(i, Integer.MAX_VALUE);
        }

        // 2.
        for (; ; ) {

            Integer finalU = u;
            graph.adjacentNodes(u).stream().filter(U::containsKey).forEach(node -> {
                Optional value = graph.edgeValue(finalU, node);
                if (value.get() + S.get(finalU) < U.get(node)) {
                    U.put(node, value.get());
                }
            });
            // 3.
            Optional> min = U.entrySet().stream().min(Comparator.comparing(Map.Entry::getValue));
            u = min.get().getKey();
            S.put(u, min.get().getValue());
            U.remove(u);
            log.info("{},{}", S, U);
            if (U.isEmpty()) {
                break;
            }
            // 4.
        }
        log.info("result {}", S);


    }
}

云服务器 GPU云服务器图算法二分图集合算法图算法 python java 图搜索算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76119.html

深度学习时代的目标检测算法

摘要：目前目标检测领域的深度学习方法主要分为两类的目标检测算法的目标检测算法。原来多数的目标检测算法都是只采用深层特征做预测，低层的特征语义信息比较少，但是目标位置准确高层的特征语义信息比较丰富，但是目标位置比较粗略。目前目标检测领域的深度学习方法主要分为两类：two stage的目标检测算法；one stage的目标检测算法。前者是先由算法生成一系列作为样本的候选框，再通过卷积神经网络进行样本...

wfc_666 2019-04-25 18:24 评论0 收藏0
js数据结构和算法（四）图和图算法

摘要：分别被命名为和。图的遍历深度优先遍历深度优先遍历，也有称为深度优先搜索，简称为。拓扑排序算法与类似，不同的是，拓扑排序算法不会立即输出已访问的顶点，而是访问当前顶点邻接表中的所有相邻顶点，直到这个列表穷尽时，才会将当前顶点压入栈中。图的定义图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G(V,E)，其中，G表示一个图，V是图G中顶点的集合，E是图G中边的...

Doyle 2019-08-21 10:22 评论0 收藏0
学习JavaScript数据结构与算法 — 图

摘要：图关联矩阵在关联矩阵表示的图中，矩阵的行表示顶点，列表示边。如图，顶点数是，边的数量是，用邻接矩阵表示图需要的空间是，而使用关联矩阵表示图需要的空间是。广度优先搜索算法数据结构是队列。深度优先搜索算法数据结构是栈。定义图和散列表、二叉树一样，是一种非线性数据结构。如图1所示，图由一系列顶点以及连接顶点的边构成。由一条边连接在一起的顶点成为相邻顶点，比如A和B、A和D是相邻的，而A和...

yiliang 2019-08-22 11:09 评论0 收藏0
Adobe提出深度抠图：利用卷积网络分离图像前景与背景

摘要：在等机构新提出的论文中，其采用了大规模数据集与深度神经网络学习图像的自然结构，从而进一步分离图像的前景与背景。一张手动抠图的前景图拥有简单背景作为输入。对于每一张测试图像，按照降序从第列到第列显示了度量下的排名结果排名到。抠图，一直是一件体力活，它需要大量的操作与时间。而传统抠图算法主要是以色彩为特征分离前景与背景，并在小数据集上完成，而这就造成了传统算法的局限性。在 Adobe 等机构新...

soasme 2019-04-25 18:10 评论0 收藏0