Message Boards Message Boards

0
|
3085 Views
|
2 Replies
|
2 Total Likes
View groups...
Share
Share this post:

Finding the shortest path when the edge weights are imaginary numbers

Is there a way to use FindShortestPath on a directed weighted graph when the weights are Complex numbers? I would like FindShortestPath to somehow use the Magnitudes of the weights as the length of the edge. I saw that there is a Method called Dijkstra that allows for positive edges. How can I get the magnitude of the weights to be used instead of the complex numbers?

POSTED BY: Henrick Jeanty
2 Replies

Thank you again Rohit, That was what I thought I might have to do. I will use that approach.

POSTED BY: Henrick Jeanty
Posted 3 years ago

Henrick,

One way would be to construct another graph with each weight replaced by its Abs value.

g1 =
  Graph[{2 \[DirectedEdge] 1, 3 \[DirectedEdge] 2, 
    4 \[DirectedEdge] 3, 4 \[DirectedEdge] 1},
   EdgeWeight -> {2 \[DirectedEdge] 1 -> 2 + 5 I, 
     3 \[DirectedEdge] 2 -> 4 - 6 I, 4 \[DirectedEdge] 3 -> 1 + 8 I, 
     4 \[DirectedEdge] 1 -> 7 - 20 I},
   VertexLabels -> "Name",
   EdgeLabels -> "EdgeWeight"];

realWeights = PropertyValue[g1, EdgeWeight] // Abs;
g2 = Graph[g1, EdgeWeight -> realWeights];
shortestPath = FindShortestPath[g2, 4, 1];

HighlightGraph[g1, PathGraph[shortestPath, DirectedEdges -> True]]

enter image description here

POSTED BY: Rohit Namjoshi
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract