有向图的邻接矩阵除了孤立顶点外，任意顶点都至少与一条边相关联，因此，任何有向图，不考虑孤立顶点，可以由其边集完全描述．有向图最短路的求解对于有向图最短路问题，计算步骤与求解无向图最短路问题相同，主要区别在于：无向图最短路问题使用单标号法。单标号法是对每一点赋予一个路权标号；而有向最短路问题使用双标号法．双标号法是对每一点赋予两个标号：路径和路权。可达性对于一个无向图来说，如果它是连通的，那么它的任意两个顶点之问必存在一条路径，因此，通过这一路径可从一个顶点“到达”另一个顶点，若从顶点“可以到达u，则从u也可以到达“，也即v和u之间是互相可以到达的。对于有向图，情形就不同了，因为存在从u到v的路径，并不蕴涵也存在从v到u的路径。设D是一个有向图，且u、v∈D，若存在从顶点u到顶点v的一条路径，则称从顶点v到顶点u可达。可达的慨念与从u到v的各种路径的数目及路径的长度无关。另外，为了完备起见，规定任一顶点到达它自身的是可达的。
一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD)为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对。相关概念孤立点：V中不与E中任一条边关联的点称为D的孤立点．简单图：无平行边的有向图称为简单图．完备图：图中任两个顶点U与u之间，恰有两条有向边(u，v)，及(v，u)，则称该有向图D为完备图．基本图：把有向图D的每条边除去定向就得到一个相应的无向图G，称G为D的基本图．称D为G的定向图．
强连通图：给定有向图G=(VE)，并且给定该图G中的任意两个结点u和v，如果结点u与结点v相互可达，即至少存在一条路径可以由结点u开始，到结点v终止，同时存在至少有一条路径可以由结点v开始，到结点u终止，那么就称该有向图G是强连通图。弱连通图:若至少有一对结点不满足单向连通，但去掉边的方向后从无向图的观点看是连通图，则D称为弱连通图．单向连通图:若每对结点至少有一个方向是连通的，则D称为单向连通图.强连通分支:有向图G的极大强连通子图称为该有向图的强连通分支。有向通路：无环有向图D中总存在这样一个独立集5，使得y—Js中任何一点"，存在H∈S，从M到"有长度不超过2的有向通路。可达性是一个有向图顶点的二元关系，依照定义，它是自反的，且是传递的。一般来说，可达不是对称的，也不是反对称的。
一个图（Graph）是表示物件与物件之间的关系的方法，是图论的基本研究对象。一个图看起来是由一些小圆点（称为顶点或结点）和连结这些圆点的直线或曲线（称为边）组成的。如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个节点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。图又有各种变体，包括简单图/多重图；有向图/无向图等，但大体上有以下两种定义方式。
