Edge-Betweenness

Shortest-path Graph

Shortest path[1] - Consider a directed network (graph) G = [N, E] with an edge length c_ij associated with each edge (i,j) in [E]. The network has a distinguished node s, called the source. The length of a directed path is defined as the sum of the lengths of edges in the path. The shortest path problem is to determine for every non-source node i in [N] a shortest length directed path from node s to node i.

Shortest-path graph[1] - In the shortest path problem, one may wish to determine a shortest path from the source node s to all other (n-1) nodes. Combining all the shortest paths together will form a shortest-path graph. It should be emphasized that the shortest-path graph for every source node will have the same number of nodes of the original graph if it is undirected. However, it is possible that there are some nodes unreachable for the source node s in a directed graph, thus the corresponding shortest-path graph may be smaller than the original graph.

Node Weight - If node weight of all upstream notes is known, weight of the node is equal to min [node weight + edge length] for all into-node-direction paths, and the edge with min [node w + edge l] is selected. In directed graph, upstream node(s) of a node refers to node(s) with edges entering the node, downstream node(s) of a node refers to node(s) with edges leaving the node.

The following example is used to explain how to find shortest-path graph. Node-1 is a source node with weight of 0. The number on side of an edge is its length.

• Node-1 weight is known 0 at the starting point;
• weight[Node-2] = 6, since its upstream node (Node-1) weight is known, and edge 1->2 is selected;
• weight[Node-3] = min [4, 6+2] = 4 and edge 1->3 is selected;
• weight[Node-5] = 6, and edge 3->5 is selected;
• At this point, weight of all upstream Nodes (2,3,5) of Node-4 are known, weight(Node-4) = min (7, 5, 8) = 5, and edge 3->4 selected
• For node-6, w = min (9, 14) = 9 and edge 5->6 selected

The node weight and edge selection process is illustrated in the following diagram. The number in the bracket following node weight is the sequence the node weight is calculated. The red check mark indicating selected edges.

The resulting shortest-path graph is shown in the following diagram:

Additional Notes:

• There should be no loop;
• If the source node has upstream node(s), all upstream node(s) will be turned off recursively.