How to find the shortest paths of a weighted direct graph represented by an incidence matrix using Dijkstra's algorithm?

Question

On the Internet, unfortunately, I only found Dijkstra’s algorithm for the adjacency matrix, but nowhere is there Dijkstra’s algorithm for the incidence matrix.

My incidence matrix (the first row of numbers are the numbers of vertices, what is in {} are edges, everything else is weight; for example, edge {1;3} with weight 5 is incident to vertex 3):

0 1 2 3 4 5 6 7

{0;1} 0 1 0 0 0 0 0 0

{0;2} 0 0 2 0 0 0 0 0

{1;2} 0 0 1 0 0 0 0 0

{1;3} 0 0 0 5 0 0 0 0

{1;4} 0 0 0 0 2 0 0 0

{2;3} 0 0 0 2 0 0 0 0

{2;4} 0 0 0 0 1 0 0 0

{2;5} 0 0 0 0 0 4 0 0

{3;4} 0 0 0 0 3 0 0 0

{3;5} 0 0 0 0 0 6 0 0

{3;6} 0 0 0 0 0 0 8 0

{4;5} 0 0 0 0 0 3 0 0

{4;6} 0 0 0 0 0 0 7 0

{5;6} 0 0 0 0 0 0 5 0

{5;7} 0 0 0 0 0 0 0 2

{6;7} 0 0 0 0 0 0 0 6

This graph:

In rectangles - the weight of the edge, and in circles just the numbers of the vertices, not the weight.

I'm trying to write an algorithm that, using Dijkstra's algorithm, will display the shortest paths from the vertex entered from the keyboard to all others, that is, the weight of the path and the path itself (the vertices through which this path passes) should be output.

I would be grateful if you help me write the algorithm =)

Just in case: I represent the matrix through a vector in the code:

vector<vector<int>> incidenceMatrix = {
  {0,1,0,0,0,0,0,0},
  {0,0,2,0,0,0,0,0},
  {0,0,1,0,0,0,0,0},
  {0,0,0,5,0,0,0,0},
  {0,0,0,0,2,0,0,0},
  {0,0,0,2,0,0,0,0},
  {0,0,0,0,1,0,0,0},
  {0,0,0,0,0,4,0,0},
  {0,0,0,0,3,0,0,0},
  {0,0,0,0,0,6,0,0},
  {0,0,0,0,0,0,8,0},
  {0,0,0,0,0,3,0,0},
  {0,0,0,0,0,0,7,0},
  {0,0,0,0,0,0,5,0},
  {0,0,0,0,0,0,0,2},
  {0,0,0,0,0,0,0,6},
};

Answer 1

By "orientated" you mean directed, I guess. Each edge allows travel in one direction only.

for example, edge {1;3} with weight 5 is incident to vertex 3

So you have an edge from 1 to 3 with weight 5. So you can add that edge to just about any graph theory library, run the Dijkstra method and get your answer without any fuss.

For example using the PathFinder library ( https://github.com/JamesBremner/PathFinder ) the input looks like this

format costs
l 0 1 1
l 0 2 2
l 1 2 1
l 1 3 5
l 1 4 2
l 2 3 2
l 2 4 1
l 2 5 4
s 0
e 4

and outputs