# Find lenght of shortest path from nodal incidence matrix

1 Ansicht (letzte 30 Tage)
Marc Gebhardt am 15 Jun. 2018
Kommentiert: Guillaume am 15 Jun. 2018
Hello, I want to find the lenght of the shortest path between two nodes out of the given nodal-terminal-incidence-matrix (nti). In the nti the number of rows equals the number of nodes and the number of columns equals the number of terminals. Every connection of two nodes is represented by a single path with two terminals. The first on the first node, second on second node. So for instance for a 4-node graph (see picture),
the nti is
KKT=[1 0 0 0 1 0 0 0;
0 1 0 0 0 0 1 0;
0 0 1 0 0 1 0 0;
0 0 0 1 0 0 0 1];
How can i calculate the adjacency-matrix from this and how can i find now the length of shortest path?
##### 1 Kommentar-1 ältere Kommentare anzeigen-1 ältere Kommentare ausblenden
Guillaume am 15 Jun. 2018
• As far as I can tell that KKT matrix tells you nothing about connectivity. It only tells you which node belongs to which terminal.
• Do the terminals actually matter. You could certainly store the adjacency matrix for the nodes and completely forget about the terminals.
• Shortest path between what and what?

Melden Sie sich an, um zu kommentieren.

### Antworten (2)

Marc Gebhardt am 15 Jun. 2018
I have already calculated the adjacence and incidence matrix with this code, where the vectors fN and tN are from-node and to-node information:
fN1=find(nti(:,:)==1);
fN=fN1(1:2:size(fN1,1)-1);
[fN,~]=ind2sub(size(nti),fN);
tN=fN1(2:2:size(fN1,1));
[tN,~]=ind2sub(size(nti),tN);
G=graph(fN,tN);
inc=incidence(G);
Now I have to find the lenght of each shortest path between two nodes.
##### 0 Kommentare-2 ältere Kommentare anzeigen-2 ältere Kommentare ausblenden

Melden Sie sich an, um zu kommentieren.

Rostislav Teryaev am 15 Jun. 2018
Bearbeitet: Rostislav Teryaev am 15 Jun. 2018
It seems not like an incidence matrix. Incidence matrix represents nodes connections. There are can be two approaches:
1. Terminals as graph nodes
IncTerminals = [1 1 0 0 1 0 0 0
1 1 0 0 0 0 1 0
0 0 1 1 0 1 0 0
0 0 1 1 0 0 0 1
1 0 0 0 1 1 0 0
0 0 1 0 1 1 0 0
0 1 0 0 0 0 1 1
0 0 0 1 0 0 1 1]
2. Nodes as graph nodes
IncNodes = [1 1 1 0
1 1 0 1
1 0 1 1
0 1 1 1]
But I can not remember wether it possible or not to convert incinence matrix to adjacency matrix or build a graph object with it.
But it is possible to build any kind of matrix or graph object if you would set edges as a pairs of nodes (check the doc for graph function). Again two ways:
1. Terminals as graph nodes
s = [1 1 2 3 3 4 5 7]; % Vector of starting nodes
t = [2 5 7 4 6 8 6 8]; % Vector of target nodes
2. Nodes as graph nodes
s = [1 1 2 3]; % Vector of starting nodes
t = [2 3 4 4]; % Vector of target nodes
Now you can create a graph object by
G = graph(s,t);
plotting it by
plot(G)
gives
1. Terminals
2. Nodes
Then you can extract from graph object any matrix you want
or
Inc = incidence(G);
And the shortest path also
P = shortestpath(G,1,3)
##### 1 Kommentar-1 ältere Kommentare anzeigen-1 ältere Kommentare ausblenden
Marc Gebhardt am 15 Jun. 2018
Yeah, but now I got it, that with
distances(G)
you can get the wanted values.

Melden Sie sich an, um zu kommentieren.

### Kategorien

Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange

### Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by