I have a weight graph, as generated by this code:
weightGraph=Graph[{SparseArray[Automatic, {55, 55},
0, {1, {{0, 2, 4, 7, 9, 12, 15, 17, 20, 23, 26, 28, 31, 34, 37, 40,
42, 45, 48, 51, 54, 57, 59, 62, 65, 68, 71, 74, 77, 79, 82, 85,
88, 91, 94, 97, 100, 102, 105, 108, 111, 114, 117, 120, 123,
126, 126, 126, 126, 126, 126, 126, 126, 126, 126,
126}, {{2}, {3}, {4}, {5}, {4}, {5}, {6}, {7}, {8}, {7}, {8},
{9}, {8}, {9}, {10}, {11}, {12}, {11}, {12}, {13}, {12}, {13}, {14},
{13}, {14}, {15}, {16}, {17}, {16}, {17}, {18}, {17}, {18}, {19},
{18}, {19}, {20}, {19}, {20}, {21}, {22}, {23}, {22}, {23}, {24},
{23}, {24}, {25}, {24}, {25}, {26}, {25}, {26}, {27}, {26}, {27},
{28}, {29}, {30}, {29}, {30}, {31}, {30}, {31}, {32}, {31}, {32},
{33}, {32}, {33}, {34}, {33}, {34}, {35}, {34}, {35}, {36}, {37},
{38}, {37}, {38}, {39}, {38}, {39}, {40}, {39}, {40}, {41}, {40},
{41}, {42}, {41}, {42}, {43}, {42}, {43}, {44}, {43}, {44}, {45},
{46}, {47}, {46}, {47}, {48}, {47}, {48}, {49}, {48}, {49}, {50},
{49}, {50}, {51}, {50}, {51}, {52}, {51}, {52}, {53}, {52}, {53},
{54}, {53}, {54}, {55}}}, Pattern}],
Null}, {EdgeWeight -> {79, 77, 59, 77, 57, 75, 109, 60, 72, 78, 90,
87, 124, 121, 149, 97, 112, 109, 124, 64, 121, 61, 146, 89, 174,
152, 139, 128, 154, 143, 120, 83, 60, 105, 145, 190, 99, 168, 77,
105, 93, 88, 82, 77, 114, 54, 91, 94, 136, 139, 173, 48, 82, 77,
110, 105, 107, 62, 104, 57, 99, 77, 136, 114, 41, 117, 44, 130,
78, 164, 101, 159, 96, 133, 98, 135, 127, 110, 78, 152, 120, 151,
98, 129, 115, 56, 42, 54, 128, 140, 89, 77, 26, 111, 63, 148, 136,
140, 128, 130, 126, 87, 94, 55, 55, 86, 86, 143, 72, 129, 111,
141, 123, 101, 72, 50, 68, 135, 153, 185, 141, 173, 129, 175, 131,
123}, VertexCoordinates -> {{0, 10}, {0, 9}, {1, 9}, {0, 8}, {1,
8}, {2, 8}, {0, 7}, {1, 7}, {2, 7}, {3, 7}, {0, 6}, {1, 6}, {2,
6}, {3, 6}, {4, 6}, {0, 5}, {1, 5}, {2, 5}, {3, 5}, {4, 5}, {5,
5}, {0, 4}, {1, 4}, {2, 4}, {3, 4}, {4, 4}, {5, 4}, {6, 4}, {0,
3}, {1, 3}, {2, 3}, {3, 3}, {4, 3}, {5, 3}, {6, 3}, {7, 3}, {0,
2}, {1, 2}, {2, 2}, {3, 2}, {4, 2}, {5, 2}, {6, 2}, {7, 2}, {8,
2}, {0, 1}, {1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}, {6, 1}, {7,
1}, {8, 1}, {9, 1}}}]
I want to find a path with maximal total edge weight from source vertex to sink vertex. This is current the brute-force method based on FindPath
path = MaximalBy[
Catenate[FindPath[weightGraph,
First[GraphComputation`SourceVertexList[weightGraph]], #,
Infinity, All] & /@
GraphComputation`SinkVertexList[weightGraph]],
Total[PropertyValue[{weightGraph, #}, EdgeWeight] & /@
EdgeList[PathGraph[#, DirectedEdges -> True]]] &]
{{35$374,42$376,67$379,82$383,92$387,98$392,75$399,89$406,51$414,90$422}}
Show the path
HighlightGraph[weightGraph, PathGraph[#, DirectedEdges -> True],
GraphHighlightStyle -> "Thick",
EdgeLabels ->
Thread[EdgeList[
PathGraph[#,
DirectedEdges ->
True]] -> (PropertyValue[{weightGraph, #}, EdgeWeight] & /@
EdgeList[PathGraph[#, DirectedEdges -> True]])]]
And the maximal path cost is
Total[PropertyValue[{weightGraph, #}, EdgeWeight] & /@
EdgeList[PathGraph[First[path], DirectedEdges -> True]]]
1317
Any higher efficient method can do this but not brute force?